Vanja and Miksi really like games. After playing one game for a long time, they decided to invent another game!
In this game, they have a sequence $A_1, A_2, \dots, A_N$ and two numbers $Z_1$ and $Z_2$. The rules of the game are as follows:
- The players take turns alternately, starting with Vanja.
- There is an integer $S$; at the beginning, $S = 0$.
- In each turn, the current player must choose an arbitrary element of $A$ and either add that number to $S$ or subtract it from $S$. Each element can be selected multiple times.
- Afterwards, if $S = Z_1$ or $S = Z_2$, the current player (the player who made $S$ equal to $Z_1$ or $Z_2$) is the winner of the game.
- If the game lasts for $10^{10}$ turns, Vanja and Miksi decide to declare it a tie.
Can you help the boys determine the winner of the game? Please note that the game can end in a tie (if nobody can make $S = Z_1$ or $S = Z_2$ in the first $10^{10}$ moves).
Both players play optimally, i.e. if there is a move which guarantees the current player's victory regardless of the other player's moves, the current player will make such a move. If the current player cannot win and there is a move which guarantees that the game will end in a tie, the current player will make such a move.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains three space-separated integers $N$, $Z_1$ and $Z_2$.
- The second line contains $N$ space-separated integers $A_1, A_2, \dots, A_N$.

-----Output-----
- For each test case, print a single line containing one integer — the final result of the game:
- $1$ if Vanja (the first player) has a winning strategy
- $2$ if Miksi (the second player) has a winning strategy
- $0$ if the game ends in a tie

-----Constraints-----
- $1 \le T \le 50$
- $1 \le N \le 50$
- $|Z_1|, |Z_2| \le 10^9$
- $|A_i| \le 10^9$ for each valid $i$

-----Subtasks-----
Subtask #1 (25 points): $N = 2$
Subtask #2 (75 points): original constraints

-----Example Input-----
3
2 6 4
-4 10
1 1 -1
2
2 0 7
3 4

-----Example Output-----
1
0
2

-----Explanation-----
Example case 1: The first player can choose the value $A_1 = -4$, subtract it from $S = 0$ and obtain $S = - (-4) = 4 = Z_2$. The winner is the first player.  
Example case 2: It can be proven that neither player is able to reach $S = Z_1$ or $S = Z_2$. The result is a tie.

Difficulty: interview

Starter code:

Solutions:
import sys
from collections import defaultdict as dd
from collections import deque
from fractions import Fraction as f
from copy import *
from bisect import * 
from heapq import *
from math import *
from itertools import permutations 
 
def eprint(*args):
 print(*args, file=sys.stderr)
zz=1
 
#sys.setrecursionlimit(10**6)
if zz:
 input=sys.stdin.readline
else:   
 sys.stdin=open('input.txt', 'r')
 sys.stdout=open('all.txt','w')
def li():
 return [int(xx) for xx in input().split()]
def fli():
 return [float(x) for x in input().split()] 
def comp(a,b):
 if(a>b):
  return 2
 return 2 if a==b else 0 
def gi():   
 return [xx for x in input().split()]
def fi():
 return int(input())
def swap(a,i,j):
 a[i],a[j]=a[j],a[i] 
def si():
 return list(input().rstrip()) 
def mi():
 return map(int,input().split()) 
def gh():
 sys.stdout.flush()
def graph(n,m):
 for i in range(m):
  x,y=mi()
  a[x].append(y)
  a[y].append(x)
def bo(i):
 return ord(i)-ord('a')
  
 
t=fi()
while t>0:
 t-=1
 n,z1,z2=mi()
 d={}
 a=li()
 flag=0
 for i in a:
  d[i]=1
  d[-i]=1
  if i==z1 or i==z2 or i==-z1 or i==-z2:
   flag=1
   break
 if flag:
  print(1)
  continue 
 for i in d:
  p=[i-z1,i-z2]
  c=1
  for j in p:
   if j in d:
    c*=0
  flag|=c 
 print(0 if flag else 2) 

# cook your dish here
for _ in range(int(input())):
 n, z1, z2 = [int(i) for i in input().split()]
 A = [int(i) for i in input().split()]
 t1 = [i for i in A] + [-i for i in A]
 if z1 in t1 or z2 in t1 :
  print(1)
 else :
  t2 = 2
  for val in t1 :
   t3 = [val + t for t in t1]
   if z1 not in t3 and z2 not in t3 :
    t2 = 0
    break
  print(t2)

t = int(input())

for _ in range(t):
 n, z1, z2 = list(map(int, input().split()))
 
 arr = list(map(int, input().split()))

 for i in range(n):
  arr[i] = abs(arr[i])

 if (abs(z1) in arr) or (abs(z2) in arr):
  print(1)
  continue

 if (z1 == 0) or (z2 == 0):
  print(2)
  continue

 poss = True
 for i in arr:
  #print(z1 + i, z2 + i, z1 - i, z2 - i)
  if ((abs(z1 + i) in arr) or (abs(z2 + i) in arr)) and \
   ((abs(z1 - i) in arr) or (abs(z2 - i) in arr)):
   pass
  else:
   poss = False
   break

 if poss:
  print(2)
  continue

 print(0)


for _ in range(int(input())):
 n,z1,z2=map(int,input().split())
 num1=[int(i) for i in input().split()]
 num2=[int(i)*-1 for i in num1]
 nums=num1+num2 
 f=0 
 if z1 in nums or z2 in nums:
  f=1 
  print(1) #can directly pick and win
  continue 
 cnt=0 
 for val in nums:
  if val-z1 in nums or val-z2 in nums:
   cnt+=1 
 if f==0 and cnt==n+n:
  print(2) #still_mate ...where ever u go..u will be killed
  f=2 
 if not f:
  print(0)

import sys 

T = int(sys.stdin.readline())
for tc in range(T):
 N,Z1,Z2 = [int(c) for c in sys.stdin.readline().strip().split()]
 A = [int(c) for c in sys.stdin.readline().strip().split()]
 A.extend([-a for a in A])
 def sol(A, Z1, Z2):        
  if Z1 in A or Z2 in A:
   return 1
  else:
   if all((Z1-s in A or Z2-s in A) for s in A):
    return 2
  return 0
 print(sol(A, Z1, Z2))
  


for T in range(0, int(input())):

 n, z1, z2 = map(int, input().split())

 x = list(map(int, input().split()))
 y = x

 for i in range(0, n):
  y.append(-x[i])

 res = 0

 for i in range(0, n):
  if (abs(x[i]) == abs(z1) or abs(x[i]) == abs(z2)):
   res = 1
   break

 if res == 0:
  for i in range(0, 2*n):
   flag = 0
   for j in range(0, 2*n):
    if y[i] + y[j] == z1 or y[i] + y[j] == z2:
     flag = 1
     break

   if flag == 0:
    break
  if flag == 1:
   res = 2


 print(res)

for i in range(int(input())):
 n,z1,z2 = map(int,input().split())
 arr = list(map(int,input().split()))
 m = dict()
 for item in arr:
  m[item]=1
  m[-item]=-1
 if z1 in m or z2 in m: 
  print("1")
 else:
  cnt = 0
  for item in arr:
   if z1-item in m or z2-item in m:
    cnt+=1
   if z1+item in m or z2+item in m:
    cnt+=1
  if cnt==2*n:
   print("2")
  else: print("0")

from collections import defaultdict
for t in range(int(input())):
 n,z1,z2=list(map(int,input().split()))
 seq=list(map(int,input().split()))
 c=0
 dic=defaultdict(int)
 for i in seq :
  dic[i]=1
  dic[-i]=1
 if dic[z1] or dic[z2]:
  print(1)
  continue
 for i in seq :
  if dic[z1-i] or dic[z2-i]:
   c+=1
  if dic[z1+i] or dic[z2+i]:
   c+=1
 if c==2*len(seq):
  print(2)
 else :
  print(0)


T = int(input())

for a in range(T):
 n, z1, z2 = map(int,input().split())
 num = [int(a) for a in input().split()][:n]
 num2 = [-1*i for i in num]
 nums = num+num2

 flag = 0
 for val in nums:
  if val == z1 or val == z2:
   flag = 1
   print(1)
   break
 cnt = 0
 for val1 in nums:
  if val1 - z1 in nums or val1 - z2 in nums:
   cnt += 1
 if cnt == len(nums) and not flag == 1:
  flag = 2
  print(2)
 if flag == 0:
  print(0)

def check(arr, z) :
 for i in arr :
  if i in z : return 1
 for i in arr :
  flag = True
  for j in arr :
   if i+j in z or i-j in z :
    flag = False
    break
  if flag : return 0
 return 2

for test_case in range(int(input())) :
 n, z1, z2 = [int(i) for i in input().split()]
 arr = [int(i) for i in input().split()]
 arr += [-i for i in arr]
 print(check(arr, (z1, z2)))

t = int(input())
while t > 0:
 inp = input()
 arr = input()
 inp = inp.split() 
 n = int(inp[0])
 z1 = int(inp[1])
 z2 = int(inp[2])
 arr = arr.split()
 arr = [int(value) for value in arr]
 for i in range(n):
  arr.append(-1 * arr[i])
 flag = 0
 for val in arr:
  if val == z1 or val == z2:
   flag = 1
   print(1)
   break
 cnt = 0
 for val1 in arr:
  if val1 - z1 in arr or val1 - z2 in arr:
   cnt += 1
 if cnt == len(arr) and not flag == 1:
  flag = 2
  print(2)
 if flag == 0:
  print(0)
 t -= 1

from itertools import chain

R = lambda: list(map(int, input().split()))
t = int(input())
for _ in range(t):
 n, *z = R()
 u = set(chain.from_iterable((x, -x) for x in R()))
 v = set(x + y for x in z for y in u)
 if 0 in v:
  print(1)
 elif u <= v:
  print(2)
 else:
  print(0)


for i in range(int(input())):
 n, a, b = [int(c) for c in input().split()]
 impossible = 0
 arr = [abs(int(x)) for x in input().split()]

 if a in arr or -a in arr or b in arr or -b in arr:
  print(1)
  continue

 if a == 0 or b == 0:
  print(2)
  continue
 if a == -b:
  for move1 in arr:
   a_left = abs(a - move1)
   b_left = abs(b - move1)
   if a_left in arr or b_left in arr:
    continue
   else:
    impossible = 1 
    break
  else:
   print(2)
   continue

 print(0)

for i in range(int(input())):
 n, a, b = [int(c) for c in input().split()]
 impossible = 0
 arr = [abs(int(x)) for x in input().split()]

 if a in arr or -a in arr or b in arr or -b in arr:
  print(1)
  continue

 if a == 0 or b == 0:
  print(2)
  continue
 if a == -b:
  for move1 in arr:
   a_left = abs(a - move1)
   b_left = abs(b - move1)
   if a_left in arr or b_left in arr:
    continue
   else:
    impossible = 1 
    break
  else:
   print(2)
   continue

 print(0)


from itertools import chain

R = lambda: list(map(int, input().split()))
t = int(input())
for _ in range(t):
 n, *z = R()
 a = list(R())
 u = set(chain.from_iterable((x, -x) for x in a))
 v = set(x + y for x in z for y in u)
 if 0 in v:
  print(1)
 elif u <= v:
  print(2)
 else:
  print(0)


from itertools import chain

R = lambda: list(map(int, input().split()))
t = int(input())
for _ in range(t):
 n, *z = R()
 a = list(R())
 aa = lambda: chain.from_iterable((x, -x) for x in a)
 v = set(x + y for x in z for y in aa())
 if 0 in v:
  print(1)
 elif set(aa()) <= v:
  print(2)
 else:
  print(0)


from itertools import chain

R = lambda: list(map(int, input().split()))
t = int(input())
for _ in range(t):
 n, *z = R()
 a = list(R())
 aa = lambda: chain.from_iterable((x, -x) for x in a)
 u = set(chain.from_iterable((x, -x) for x in a))
 v = set(x + y for x in z for y in aa())
 if 0 in v:
  print(1)
 elif set(aa()) <= v:
  print(2)
 else:
  print(0)


from itertools import chain

R = lambda: list(map(int, input().split()))
t = int(input())
for _ in range(t):
 n, *z = R()
 a = list(R())
 u = set(chain.from_iterable((x, -x) for x in a))
 v = set(x + y for x in z for y in u)
 if 0 in v:
  print(1)
 elif u <= v:
  print(2)
 else:
  print(0)


t=int(input())
for _ in range(t):
 n,z1,z2=map(int,input().split())
 l = list(map(int,input().split()))
 if z1 in l or z2 in l or -1*z1 in l or -1*z2 in l:
  print(1)
  continue
 if z1==0 and z2==0:
  print(2)
  continue
 l=list(map(abs,l))
 for i in l:
  if abs(z1-i) not in l and abs(z2-i) not in l:
   print(0)
   break
  if abs(z1+i) not in l and abs(z2+i) not in l:
   print(0)
   break
 else:
  print(2)

from itertools import chain
from functools import reduce
from operator import and_

R = lambda: list(map(int, input().split()))
t = int(input())
for _ in range(t):
 n, *z = R()
 a = list(R())
 aa = lambda: chain.from_iterable((x, -x) for x in a)
 r = 0
 v = [x + y for x in z for y in aa()]
 if 0 in v:
  print(1)
 elif 0 in reduce(and_, (set(x + y for x in v) for y in aa())):
  print(2)
 else:
  print(0)