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: HARD
Tags: Game theory

Ad-hoc

Starter code:

Solutions:
from functools import reduce
from operator import and_
R = lambda : map(int, input().split())
S = (-1, 1)
t = int(input())
for _ in range(t):
	(n, z1, z2) = R()
	a = list(R())
	m = {z1, z2}
	while True:
		v = set((x + y * s for x in m for y in a for s in S))
		if 0 in v:
			print(1)
			break
		mn = reduce(and_, (set((x + y * s for x in v)) for y in a for s in S))
		if 0 in mn:
			print(2)
			break
		if mn == m:
			print(0)
			break
		m = mn


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
		elif all((Z1 - s in A or Z2 - s in A for s in A)):
			return 2
		return 0
	print(sol(A, Z1, Z2))


t = int(input())
while t:
	t -= 1
	(n, z1, z2) = map(int, input().split())
	li = [int(x) for x in input().split()]
	a = 1
	b = 1
	c = 1
	if z1 in li or z2 in li or -1 * z1 in li or (-1 * z2 in li):
		print('1')
		continue
	if z1 == 0 or z2 == 0:
		print('2')
		continue
	for value in li:
		if abs(z1 - value) not in list(map(abs, li)) and abs(z2 - value) not in list(map(abs, li)):
			a = 0
			break
		if abs(z1 + value) not in list(map(abs, li)) and abs(z2 + value) not in list(map(abs, li)):
			b = 0
			break
	if a == 0 or b == 0:
		print('0')
		continue
	else:
		print('2')
		continue


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 itertools import chain
from functools import reduce
from operator import and_
R = lambda : map(int, input().split())
t = int(input())
for _ in range(t):
	(n, z1, z2) = R()
	a = list(R())
	aa = lambda : chain.from_iterable(((x, -x) for x in a))
	m = {z1, z2}
	while True:
		v = set((x + y for x in m for y in aa()))
		if 0 in v:
			print(1)
			break
		(mo, m) = (m, reduce(and_, (set((x + y for x in v)) for y in aa())))
		if 0 in m:
			print(2)
			break
		if m == mo:
			print(0)
			break


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)


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)
		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)
		f = 2
	if not f:
		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)


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 main():
	t = int(input())
	for _ in range(t):
		(n, z1, z2) = [int(x) for x in input().split()]
		a = [abs(int(x)) for x in input().split()]
		a = set(a)
		if z1 in a or -z1 in a or z2 in a or (-z2 in a):
			print(1)
		elif z1 == 0 or z2 == 0:
			if 0 in a:
				print(1)
			else:
				print(2)
		else:
			pivot = False
			for e in a:
				if abs(z1 - e) not in a and abs(z2 - e) not in a:
					print(0)
					break
				elif abs(z1 + e) not in a and abs(z2 + e) not in a:
					print(0)
					break
			else:
				print(2)
main()


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)))


def check(s, z1, z2):
	s1 = [0] * len(s)
	for i in range(len(s)):
		s1[i] = -s[i]
	for i in range(len(s)):
		f1 = False
		f2 = False
		for j in range(len(s)):
			if s[i] + s[j] == z1 or s[i] - s[j] == z1 or s[i] + s[j] == z2 or (s[i] - s[j] == z2):
				f1 = True
			if -s[i] + s[j] == z1 or -s[i] - s[j] == z1 or -s[i] + s[j] == z2 or (-s[i] - s[j] == z2):
				f2 = True
		if not f1 or not f2:
			return False
	return True
t = int(input())
while t > 0:
	s = input().split(' ')
	n = int(s[0])
	z1 = int(s[1])
	z2 = int(s[2])
	s1 = input().split(' ')
	for i in range(n):
		s1[i] = int(s1[i])
	f = False
	ans = 0
	if s1.count(z1) > 0 or s1.count(z2) > 0 or s1.count(-z1) > 0 or (s1.count(-z2) > 0):
		ans = 1
	else:
		if z1 == 0 or z2 == 0:
			ans = 2
		if check(s1, z1, z2):
			ans = 2
	print(ans)
	t = t - 1


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)


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:
		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)


def mix():
	n = int(input())
	while n > 0:
		l = []
		l = input().split()
		a = int(l[0])
		z1 = int(l[1])
		z2 = int(l[2])
		m = []
		m1 = []
		m = input().split()
		count = 0
		rocku = 0
		rockon = 0
		rockunism = 0
		for i in range(len(m)):
			d = int(m[i])
			m1.append(d)
			if d == z1 or d == z2 or d == -z1 or (d == -z2):
				count = count + 1
		if count > 0:
			print('1')
		else:
			for i in range(len(m1)):
				for j in range(len(m1)):
					if m1[j] - m1[i] == z1 or m1[j] - m1[i] == z2 or -m1[j] - m1[i] == z1 or (-m1[j] - m1[i] == z2):
						rocku = rocku + 1
					if m1[i] + m1[j] == z1 or m1[i] + m1[j] == z2 or m1[i] - m1[j] == z1 or (m1[i] - m1[j] == z2):
						rockon = rockon + 1
				if rocku > 0 and rockon > 0:
					rockunism = rockunism + 1
					rocku = 0
					rockon = 0
			if rockunism == a:
				print('2')
			else:
				print('0')
		n = n - 1
mix()


from math import ceil
t = int(input())
for test in range(1, t + 1):
	(n, z1, z2) = map(int, input().split())
	a = list(map(int, input().split()))
	winner = 2
	tmp = set([z1, z2])
	for i in a:
		if i in tmp or -i in tmp:
			winner = 1
			break
	if winner == 1:
		print(1)
	else:
		for i in a:
			flag = 0
			for j in a:
				if i + j in tmp or i - j in tmp:
					flag = 1
					break
			if flag == 0:
				winner = 0
				break
		for i in a:
			flag = 0
			for j in a:
				if -i + j in tmp or -i - j in tmp:
					flag = 1
					break
			if flag == 0:
				winner = 0
				break
		print(winner)


for _ in range(int(input())):
	(N, Z1, Z2) = [int(x) for x in input().split()]
	A = [abs(int(x)) for x in input().split()]
	if any((a == abs(Z1) for a in A)) or any((a == abs(Z2) for a in A)):
		print(1)
		continue
	if Z1 == 0 or Z2 == 0:
		print(2)
		continue
	if Z1 == -Z2:
		for player1Move in A:
			neededForZ1 = abs(Z1 - player1Move)
			neededForZ2 = abs(Z2 - player1Move)
			if neededForZ1 in A or neededForZ2 in A:
				continue
			else:
				break
		else:
			print(2)
			continue
	print(0)


t = int(input())
for i in range(t):
	(n, k1, k2) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	sa = set()
	for j in arr:
		sa.add(k1 + j)
		sa.add(k1 - j)
		sa.add(k2 + j)
		sa.add(k2 - j)
	sa = set(sorted(sa))
	if 0 in sa:
		print('1')
		continue
	w = 2
	for j in arr:
		if j not in sa or -j not in sa:
			w = 0
			break
	print(w)


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
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)


T = int(input())
for t in range(T):
	(n, z1, z2) = [int(i) for i in input().split(' ')]
	A = [int(i) for i in input().split(' ')]
	k = 1
	done = 0
	if abs(z1) in [abs(i) for i in A] or abs(z2) in [abs(i) for i in A]:
		print(1)
		done = 1
	else:
		ct = 0
		for i in range(n):
			k = 0
			for j in range(n):
				if (A[i] + A[j] in [z1, z2] or A[i] - A[j] in [z1, z2]) and (A[j] - A[i] in [z1, z2] or -A[j] - A[i] in [z1, z2]):
					k = 1
			if k:
				ct += 1
		if ct == n:
			print(2)
			done = 1
	if done == 0:
		print(0)


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)


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


for i in range(0, int(input())):
	(n, z1, z2) = map(int, input().split())
	my_list = list(map(int, input().split()))
	flag1 = 1
	flag2 = 1
	flag3 = 1
	if z1 in my_list or z2 in my_list or -1 * z1 in my_list or (-1 * z2 in my_list):
		print(1)
		continue
	if z1 == 0 or z2 == 0:
		print(2)
		continue
	for item in my_list:
		if abs(z1 - item) not in list(map(abs, my_list)) and abs(z2 - item) not in list(map(abs, my_list)):
			flag1 = 0
		if abs(z1 + item) not in list(map(abs, my_list)) and abs(z2 + item) not in list(map(abs, my_list)):
			flag2 = 0
	if flag1 == 0 or flag2 == 0:
		print(0)
		continue
	else:
		print(2)
		continue


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 _ 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)


I = lambda : list(map(int, input().split()))
(test,) = I()
while test:
	test -= 1
	(n, *z) = I()
	l = I()
	res = 0
	for i in l:
		if i in z or -i in z:
			res = 1
			break
	a = [0] * n
	if res == 0:
		if 0 in z:
			res = 2
		else:
			for i in range(n):
				for j in range(n):
					if (l[i] + l[j] in z or l[i] - l[j] in z) and (-l[i] + l[j] in z or -l[i] - l[j] in z):
						a[i] = 1
						break
	if all(a):
		res = 2
	print(res)


T = int(input())
for i in range(0, T):
	(N, Z1, Z2) = map(int, input().split())
	s = [int(x) for x in input().split()]
	for j in range(0, len(s)):
		s[j] = abs(s[j])
	if abs(Z1) in s or abs(Z2) in s:
		print(1)
		continue
	if Z1 == 0 or Z2 == 0:
		print(2)
		continue
	ans = 0
	for k in s:
		if (abs(Z1 + k) in s or abs(Z2 + k) in s) and (abs(Z1 - k) in s or abs(Z2 - k) in s):
			pass
		else:
			ans = 1
			break
	if ans == 0:
		print(2)
		continue
	print(0)


for i in range(int(input())):
	(n, z1, z2) = map(int, input().split())
	l = list(map(int, input().split()))
	f = 0

	def final(a, b):
		if a == b or -a == b:
			return True
		return False
	for i in range(n):
		if final(l[i], z1) or final(l[i], z2):
			f = 1
			break
	if f == 1:
		print('1')
		continue
	f = 1
	for i in range(n):
		f2 = 0
		for j in range(n):
			if (final(l[j], z1 - l[i]) or final(l[j], z2 - l[i])) and (final(l[j], z1 + l[i]) or final(l[j], z2 + l[i])):
				f2 = 1
				break
		if f2 == 0:
			f = 0
	if f != 1:
		print('0')
	else:
		print('2')


from itertools import chain
from functools import reduce
from operator import and_
R = lambda : 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)


def solve(x, y, a):
	a = [abs(z) for z in a]
	if x > y:
		(x, y) = (y, x)
	win = set()
	for z in a:
		win.update([x - z, y - z, x + z, y + z])
	if 0 in win:
		return 1
	if all((z in win for z in a)) and all((-z in win for z in a)):
		return 2
	return 0
t = int(input())
for i in range(t):
	(n, z1, z2) = map(int, input().split())
	a = list(map(int, input().split()))
	q = solve(z1, z2, a)
	print(q)


from sys import stdin
input = stdin.readline

def answer():
	if z1 in a or z2 in a or -z1 in a or (-z2 in a):
		return 1
	count = 0
	for i in range(n):
		if z1 - a[i] in a or -(z1 - a[i]) in a:
			count += 1
		elif z2 - a[i] in a or -(z2 - a[i]) in a:
			count += 1
		if z1 + a[i] in a or -(z1 + a[i]) in a:
			count += 1
		elif z2 + a[i] in a or -(z2 + a[i]) in a:
			count += 1
	if count == 2 * n:
		return 2
	return 0
for T in range(int(input())):
	(n, z1, z2) = map(int, input().split())
	a = list(map(int, input().split()))
	print(answer())


for _ in range(int(input())):
	(n, z1, z2) = map(int, input().split())
	a = list(map(int, input().split()))
	c = []
	b = []
	ab = []
	for i in a:
		b.append(i)
		b.append(-i)
		ab.append(abs(i))
	ans = 0
	for i in ab:
		if i == abs(z1) or i == abs(z2):
			ans = 1
	if ans == 0:
		for i in b:
			count = 0
			for j in b:
				if i + j != z1 and i + j != z2:
					count += 1
			c.append(count)
	if ans == 1:
		print(1)
	elif n * 2 in c:
		print(0)
	else:
		print(2)


t = int(input())
while t > 0:
	t -= 1
	(n, z1, z2) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	b = [abs(x) for x in arr]
	f = 0
	for ele in b:
		if ele == abs(z1) or ele == abs(z2):
			f = 1
			break
	if f:
		ans = 1
	elif z1 == 0 or z2 == 0:
		ans = 2
	else:
		f1 = 0
		for ele in b:
			if abs(ele - z1) not in b and abs(ele - z2) not in b or (abs(z1 + ele) not in b and abs(z2 + ele) not in b):
				f1 = 1
		if f1 == 1:
			ans = 0
		else:
			ans = 2
	print(ans)


def solve(x, y, a):
	a = [abs(z) for z in a]
	if x > y:
		(x, y) = (y, x)
	win = set()
	for z in a:
		win.update([x - z, y - z, x + z, y + z])
	if 0 in win:
		return 1
	if all((z in win for z in a)) and all((-z in win for z in a)):
		return 2
	return 0
import sys
f = sys.stdin
t = int(f.readline())
for i in range(t):
	(n, z1, z2) = map(int, f.readline().split())
	a = list(map(int, f.readline().split()))
	q = solve(z1, z2, a)
	print(q)


def main():
	t = int(input())
	for _ in range(t):
		(n, a, b) = list(map(int, input().split()))
		ar = list(map(int, input().split()))
		d = {}
		for i in range(n):
			d[ar[i]] = 1
			d[-ar[i]] = 1
		if a in d or b in d:
			print(1)
			continue
		else:
			count = 0
			for i in range(n):
				if a - ar[i] in d or b - ar[i] in d:
					count += 1
				if a + ar[i] in d or b + ar[i] in d:
					count += 1
			if count == 2 * n:
				print(2)
			else:
				print(0)
main()


for _ in range(int(input())):
	(n, x, y) = map(int, input().split())
	a = list(map(int, input().split()))
	f = 0
	c = 0
	for i in range(n):
		if abs(a[i]) == abs(x) or abs(a[i]) == abs(y):
			f = 1
			break
	if f == 1:
		print(1)
		continue
	(s, k) = (0, 0)
	for i in range(n):
		(s, k) = (0, 0)
		s += a[i]
		for j in range(n):
			if s + a[j] == x or s + a[j] == y or s - a[j] == x or (s - a[j] == y):
				k = 1
				break
		c += k
		(s, k) = (0, 0)
		s -= a[i]
		for j in range(n):
			if s + a[j] == x or s + a[j] == y or s - a[j] == x or (s - a[j] == y):
				k = 1
				break
		c += k
	if c == n * 2:
		print(2)
	else:
		print(0)


for _ in range(int(input())):
	(n, z1, z2) = map(int, input().split())
	plays = set(map(lambda x: abs(int(x)), input().strip().split()))
	res = 2
	for p in plays:
		if p == abs(z1) or p == abs(z2):
			res = 1
			break
	if res == 2:
		for p in plays:
			if not ((abs(p - z1) in plays or abs(p - z2) in plays) and (abs(p + z1) in plays or abs(p + z2) in plays)):
				res = 0
				break
	print(res)