Vanja and Miksi have already finished everything for this year at their university, so they decided to spend their free time playing a game with a binary sequence $A_1, A_2, \dots, A_N$ (i.e. a sequence containing only integers $0$ and $1$).
At the beginning of the game, Vanja and Miksi write down the expression $* A_1 * A_2 * A_3 * \ldots * A_N$ (note below that each $*$ is a placeholder and does not denote multiplication).
The players take turns alternately, starting with Vanja. The game lasts $N$ turns. In each turn, the current player must replace the first (leftmost) remaining $*$ by the sign $+$ or $-$ (or, equivalently, by the operation of addition or subtraction).
After the last turn, the boys calculate the resulting value $V$ of the expression. If $|V| \ge K$, the winner is Vanja; otherwise, the winner is Miksi.
Please predict the winner of the game if both players play optimally. 

-----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 two space-separated integers $N$ and $K$.
- 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 — $1$ if Vanja (the first player) is the winner or $2$ if Miksi (the second player) is the winner.

-----Constraints-----
- $1 \le T \le 50$
- $1 \le N \le 3 \cdot 10^4$
- $0 \le K \le 3 \cdot 10^4$
- $0 \le A_i \le 1$ for each valid $i$

-----Example Input-----
2
2 1
1 0
3 5
0 1 0

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

-----Explanation-----
Example case 1: $K = 1$, so if Vanja replaces the first $*$ by $+$, the value of the final expression will be $V = 1$; then, $K \le |V|$, so the winner is Vanja.
Example case 2: $K = 5$, but the absolute value of the final expression cannot be greater than $1$. The winner is Miksi.

Difficulty: MEDIUM_HARD
Tags: Implementation

Starter code:

Solutions:
test = int(input())
for _ in range(test):
	(n, k) = map(int, input().split())
	x = list(map(int, input().split()))
	c = 0
	for i in range(n):
		if i % 2 == 0:
			if c < 0:
				c -= x[i]
			else:
				c += x[i]
		elif c < 0:
			c += x[i]
		else:
			c -= x[i]
	if abs(c) >= k:
		print(1)
	else:
		print(2)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	v = 0
	for (j, i) in enumerate(a):
		if j % 2 == 0:
			if v < 0:
				v -= i
			else:
				v += i
		elif v >= 0:
			v -= i
		else:
			v += i
	if abs(v) >= k:
		print(1)
	else:
		print(2)


import math
T = int(input())
for j in range(T):
	(N, K) = [int(j) for j in input().split()]
	s = list(map(int, input().split()))
	sum = s[0]
	for i in range(N - 1):
		if i % 2 == 0:
			if sum >= 0:
				sum -= s[i + 1]
			else:
				sum += s[i + 1]
		elif sum >= 0:
			sum += s[i + 1]
		else:
			sum -= s[i + 1]
	if math.fabs(sum) >= K:
		print('1')
	else:
		print('2')


t = int(input())
while t:
	s = input()
	a = s.split()
	n = int(a[0])
	k = int(a[1])
	ans = 0
	s = input()
	l = s.split()
	for i in range(0, n):
		if l[i] == '1':
			ans = 1
			i = i + 1
			break
	while i < n:
		if l[i] == '1' and i % 2 == 0:
			ans = ans + 1
		elif l[i] == '1' and ans > 0:
			ans = ans - 1
		elif l[i] == '1' and ans <= 0:
			ans = ans + 1
		i = i + 1
	if k <= ans:
		print('1')
	else:
		print('2')
	t = t - 1


t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	v = 0
	for j in range(n):
		if j % 2 == 0:
			if v < 0:
				v -= l[j]
			else:
				v += l[j]
		elif v < 0:
			v += l[j]
		else:
			v -= l[j]
	print('1' if abs(v) >= k else '2')


class Solution(object):

	def __init__(self):
		self.t = int(input())
		for _ in range(self.t):
			(n, k) = map(int, input().split())
			a = list(map(int, input().split()))
			s = 0
			for i in range(n):
				if i & 1:
					if s >= 0:
						s -= a[i]
					else:
						s += a[i]
				elif s >= 0:
					s += a[i]
				else:
					s -= a[i]
			if abs(s) >= k:
				print(1)
			else:
				print(2)
	pass

	@classmethod
	def create_test(cls):
		t_limit = 50
		from random import randint, choice
		t = randint(1, t_limit)
		print(t)
		n_limit = 10
		k_limit = 10
		a = [0, 1]
		for _ in range(t):
			n = randint(1, n_limit)
			k = randint(0, k_limit)
			print('%d %d' % (n, k))
			for _ in range(n):
				x = choice(a)
				print(x, end=' ')
			print()
		exit(0)
		pass
obj = Solution()


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	seq = [int(i) for i in input().split()]
	value = 0
	turn = 0
	for i in range(N):
		if seq[i] == 0:
			value += seq[i]
			turn = int(not turn)
		elif turn == 0:
			if K - abs(value + 1) <= K - abs(value - 1):
				value += 1
				turn = 1
			else:
				value -= 1
				turn = 1
		elif K - abs(value + 1) <= K - abs(value - 1):
			value -= 1
			turn = 0
		else:
			value += 1
			turn = 0
	if abs(value) >= K:
		print(1)
	else:
		print(2)


t = int(input())
for j in range(t):
	(n, k) = map(int, input().split())
	s = list(map(int, input().split()))
	sum = 0
	for i in range(0, n - 1, 2):
		if sum >= 0:
			sum += s[i]
		else:
			sum -= s[i]
		if sum >= 0:
			sum -= s[i + 1]
		else:
			sum += s[i + 1]
	if n % 2 != 0:
		if sum <= 0:
			sum -= s[n - 1]
		else:
			sum += s[n - 1]
	if k <= abs(sum):
		print(1)
	else:
		print(2)


def integer_list():
	return list(map(int, input().split()))

def string_list():
	return list(map(str, input().split()))

def hetro_list():
	return list(input().split())
import math
from collections import Counter

def solve():
	v1 = 0
	for (i, v) in enumerate(lst):
		if i % 2 == 0:
			if v1 < 0:
				v1 -= v
			else:
				v1 += v
		elif v1 > 0:
			v1 -= v
		else:
			v1 += v
	if abs(v1) >= k:
		print(1)
	else:
		print(2)
t = int(input())
for _ in range(t):
	(n, k) = integer_list()
	lst = integer_list()
	solve()


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	sum1 = 0
	for i in range(n):
		if i % 2 == 0:
			if sum1 >= 0:
				sum1 += arr[i]
			elif sum1 < 0:
				sum1 -= arr[i]
		elif sum1 >= 0:
			sum1 -= arr[i]
		elif sum1 < 0:
			sum1 += arr[i]
	if abs(sum1) >= k:
		print('1')
	else:
		print('2')


def mixi_game(n, k, arr):
	val = 0
	for i in range(n):
		if i % 2 == 0:
			if val < 0:
				val -= arr[i]
			else:
				val += arr[i]
		elif val < 0:
			val += arr[i]
		else:
			val -= arr[i]
	if k <= abs(val):
		return 1
	else:
		return 2
t = int(input())
for i in range(t):
	(n, k) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	print(mixi_game(n, k, arr))


from sys import stdin, stdout
import math
from collections import Counter
import functools
import time

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

def line():
	return stdin.readline().rstrip()

def b(x):
	return bin(x).replace('0b', '')

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)) + '\n')

def main():
	for _ in tr():
		(n, k) = sm()
		a = ln()
		sum_so_far = 0
		for i in range(n):
			if a[i] == 0:
				continue
			if i & 1:
				if sum_so_far <= 0:
					sum_so_far += a[i]
				else:
					sum_so_far -= a[i]
			elif sum_so_far >= 0:
				sum_so_far += a[i]
			else:
				sum_so_far -= a[i]
		if abs(sum_so_far) >= k:
			print('1')
		else:
			print('2')
main()


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = 0
	for i in range(n):
		if i % 2 == 0:
			if s >= 0:
				s += a[i]
			else:
				s -= a[i]
		elif s >= 0:
			s -= a[i]
		else:
			s += a[i]
	if abs(s) >= k:
		print(1)
	else:
		print(2)
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	s = 0
	for i in range(n):
		if l[i] == 1:
			if i & 1 and s > 0:
				s -= 1
			elif i & 1:
				s += 1
			elif s >= 0:
				s += 1
			else:
				s -= 1
	if abs(s) < k:
		print('2')
	else:
		print('1')


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = input().split()
	s = 0
	for j in range(len(l)):
		if j % 2 == 0 and l[j] == '1':
			if s >= 0:
				s += 1
			else:
				s -= 1
		elif l[j] == '1':
			if s >= 0:
				s -= 1
			else:
				s += 1
	if abs(s) >= k:
		print(1)
	else:
		print(2)


for i in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	sm = 0
	for i in range(n):
		if i % 2 == 0:
			if sm < 0:
				sm -= a[i]
			else:
				sm += a[i]
		elif sm < 0:
			sm += a[i]
		else:
			sm -= a[i]
	if abs(sm) >= k:
		print(1)
	else:
		print(2)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		if i % 2 == 0:
			if ans > 0:
				ans += l[i]
			else:
				ans -= l[i]
		elif ans > 0:
			ans -= l[i]
		else:
			ans += l[i]
	if abs(ans) >= k:
		print(1)
	else:
		print(2)


t = int(input())
for x in range(t):
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	s = 0
	for i in range(0, n):
		if i % 2 == 0:
			s += a[i]
		elif s > 0:
			s -= a[i]
		else:
			s += a[i]
	if s >= k:
		print(1)
	else:
		print(2)


def checkClosest(x, k):
	if abs(-k - x) > abs(k - x):
		return False
	else:
		return True
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	nums = list(map(int, input().split()))
	curr = 0
	for idx in range(n):
		if idx % 2:
			if checkClosest(curr, k):
				curr += nums[idx]
			else:
				curr -= nums[idx]
		elif checkClosest(curr, k):
			curr -= nums[idx]
		else:
			curr += nums[idx]
	if abs(curr) >= k:
		print(1)
	else:
		print(2)


def m():
	t = int(input())
	l = []
	m = []
	w = []
	a = []
	while t > 0:
		a = input().split()
		n = int(a[0])
		k = int(a[1])
		l = input().split()
		for i in range(n):
			q = int(l[i])
			m.append(q)
			w.append(0)
			if i % 2 == 0:
				w[i] = 1
			else:
				w[i] = 2
		sum1 = 0
		for i in range(n):
			if w[i] == 1:
				if sum1 >= 0:
					sum1 = sum1 + m[i]
				else:
					sum1 = sum1 - m[i]
			elif sum1 >= 0:
				sum1 = sum1 - m[i]
			else:
				sum1 = sum1 + m[i]
		res = abs(sum1)
		if res >= k:
			print(1)
		else:
			print(2)
		l = []
		m = []
		w = []
		a = []
		t = t - 1
m()


t = int(input())
for i in range(t):
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	ans = 0
	for j in range(a[0]):
		if j % 2 == 0:
			if b[j] == 1:
				if ans >= 0:
					ans += 1
				else:
					ans = ans - 1
		elif b[j] == 1:
			if ans >= 0:
				ans = ans - 1
			else:
				ans += 1
	if abs(ans) >= a[1]:
		print(1)
	else:
		print(2)


def val(a, x):
	v = 0
	f = 0
	i = 0
	while i < x:
		if a[i] == '+':
			v = v + int(a[i + 1])
			i += 1
		elif a[i] == '-':
			v = v - int(a[i + 1])
			i += 1
		i += 1
	return v

def fun(a, n, k):
	f = 0
	v = 0
	for i in range(n):
		if i % 2 == 0:
			if i == 0:
				v = 0
			elif a[i - 2] == '+':
				v = v + int(a[i - 1])
			else:
				v = v - int(a[i - 1])
			if v >= 0:
				if f % 2 == 0:
					a[i] = '+'
				else:
					a[i] = '-'
			elif f % 2 == 0:
				a[i] = '-'
			else:
				a[i] = '+'
			f += 1
	v = val(a, n - 2)
	if abs(v) >= k:
		print(1)
	else:
		print(2)
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	a = []
	p = 0
	for j in range(2 * n + 1):
		if j % 2 == 0:
			a.append('*')
		else:
			a.append(str(l[p]))
			p += 1
	fun(a, 2 * n + 1, k)


t = int(input())
for uu in range(0, t):
	(n, k) = map(int, input().rstrip().split())
	li = list(map(int, input().rstrip().split()))
	su = 0
	for i in range(0, n):
		if i % 2 == 0:
			if li[i] and 1:
				if su > 0:
					su = su + li[i]
				else:
					su = su - li[i]
		elif li[i] and 1:
			if su > 0:
				su = su - 1
			else:
				su = su + 1
	if abs(su) >= k:
		print(1)
	else:
		print(2)


import math
import sys

def _int():
	return int(sys.stdin.readline())

def _ints():
	return map(int, sys.stdin.readline().split())

def _intarr():
	return list(map(int, sys.stdin.readline().split()))

def _str():
	return sys.stdin.readline()

def _strarr():
	return sys.stdin.readline().split()
t = _int()
for _ in range(t):
	(n, k) = _ints()
	a = _intarr()
	v = 0
	for i in range(n):
		if a[i] == 1:
			if i % 2 == 0:
				if v > 0:
					v += 1
				else:
					v -= 1
			elif v > 0:
				v -= 1
			else:
				v += 1
	print(1 if abs(v) >= k else 2)


t = int(input())
while t != 0:
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()[:n]))
	s = 0
	v = True
	for i in a:
		if v or s == 0:
			s += i
		else:
			s -= i
		v = not v
	if s >= k:
		print('1')
	else:
		print('2')
	t -= 1


test_cases = int(input())
result = []
for i in range(test_cases):
	(n, k) = map(int, input().split())
	alist = list(map(int, input().split()))
	ans = 0
	asum = 0
	for j in range(n):
		if asum >= 0 and ans == 0:
			asum = alist[j] + asum
			ans = 1
		elif asum >= 0 and ans == 1:
			asum = asum - alist[j]
			ans = 0
		elif asum < 0 and ans == 0:
			asum = alist[j] - asum
			ans = 1
		elif asum < 0 and ans == 1:
			asum = asum + alist[j]
			ans = 0
	if k == 0:
		result.append(1)
	elif abs(asum) >= k:
		result.append(1)
	else:
		result.append(2)
for i in result:
	print(i)


T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	L = list(map(int, input().split()))
	ans = 0
	minus1 = 0
	plus1 = 0
	for i in range(n):
		if i % 2 == 0:
			if L[i] == 1:
				if minus1 > plus1:
					ans -= L[i]
					minus1 += 1
				else:
					ans += L[i]
					plus1 += 1
			else:
				pass
		elif L[i] == 1:
			if minus1 > plus1:
				ans += L[i]
				plus1 += 1
			else:
				ans -= L[i]
				minus1 += 1
		else:
			pass
	if abs(ans) >= k:
		print(1)
	else:
		print(2)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	x = 0
	for i in range(len(l)):
		if i % 2 == 0:
			if x >= 0:
				x += l[i]
			else:
				x -= l[i]
		elif x >= 0:
			x -= l[i]
		else:
			x += l[i]
	if abs(x) >= k:
		print(1)
	else:
		print(2)


for i in range(int(input())):
	(n, k) = (int(s) for s in input().split())
	l = [int(s) for s in input().split()]
	ans = 0
	for j in range(n):
		if j % 2 == 0:
			if l[j] == 1:
				if ans >= 0:
					ans += 1
				else:
					ans -= 1
		elif l[j] == 1:
			if ans > 0:
				ans -= 1
			else:
				ans += 1
	if abs(ans) >= k:
		print(1)
	else:
		print(2)


t = int(input())
for i in range(t):
	(N, K) = input().split()
	sum = 0
	a = list(map(int, input().split()))
	for j in range(0, int(N)):
		if a[j] == 0:
			continue
		if j % 2 == 0:
			sum = abs(sum) + a[j]
		else:
			sum = abs(sum) - a[j]
	if abs(sum) >= int(K):
		print('1')
	else:
		print('2')


t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	total = 0
	for (i, ai) in enumerate(arr):
		if ai == 0:
			continue
		if i % 2 == 0:
			if total >= 0:
				total += 1
			elif total < 0:
				total -= 1
		elif total > 0:
			total -= 1
		else:
			total += 1
	if abs(total) >= k:
		print(1)
	else:
		print(2)


for _ in range(int(input().strip())):
	(n, k) = list(map(int, input().strip().split()))
	total = 0
	player = 0
	for i in map(int, input().strip().split()):
		if player == 0:
			if total < 0:
				total -= i
			else:
				total += i
			player = 1
		else:
			if total < 0:
				total += i
			else:
				total -= i
			player = 0
	if abs(total) >= k:
		print(1)
	else:
		print(2)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	y = []
	y = [x for x in input().split(' ')]
	y = [int(k) for k in y]
	m = len(y)
	j = 0
	s = 0
	while j < m:
		if j == 0:
			s = y[j]
		elif j % 2 == 0 and y[j] == 1:
			if s > 0:
				s = s + 1
			else:
				s = s - 1
		elif j % 2 != 0 and y[j] == 1:
			if s > 0:
				s = s - 1
			else:
				s = s + 1
		j = j + 1
	if abs(s) >= k:
		print(1)
	else:
		print(2)


for z in range(int(input())):
	(n, k) = (int(x) for x in input().split())
	ar = [int(x) for x in input().split()]
	(s, sign) = (0, 0)
	for i in range(n):
		if i % 2 == 0:
			if s > 0:
				sign = 1
			else:
				sign = 0
		elif s > 0:
			sign = 0
		else:
			sign = 1
		if sign == 1:
			s += ar[i]
		else:
			s -= ar[i]
	if abs(s) < k:
		print('2')
	else:
		print('1')


for t in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	v = 0
	for i in range(n):
		if i % 2 == 0:
			v = max(abs(v + a[i]), abs(v - a[i]))
		else:
			v = min(abs(v + a[i]), abs(v - a[i]))
	if v >= k:
		print(1)
	else:
		print(2)


for i in range(int(input())):
	(n, k) = list(map(int, input().split()))
	j = list(map(int, input().split()))
	s = 0
	t = 0
	while n > 0:
		if s >= 0 and t == 0:
			s += j.pop(0)
			t = 1
			n -= 1
		elif s < 0 and t == 0:
			s -= j.pop(0)
			t = 1
			n -= 1
		elif s >= 0 and t == 1:
			s -= j.pop(0)
			t = 0
			n -= 1
		elif s < 0 and t == 1:
			s += j.pop(0)
			t = 0
			n -= 1
	if abs(s) >= k:
		print('1')
	else:
		print('2')


import math
t = int(input())
one = 1
two = 2
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = 0
	for i in range(n):
		s += a[i]
	if s < k:
		print(two)
	else:
		s = 0
		for i in range(n):
			if i % 2 == 0:
				s += a[i]
			elif s > 0:
				s -= a[i]
			else:
				s += a[i]
		if abs(s) >= k:
			print(one)
		else:
			print(two)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ar = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		if i % 2 == 0:
			ans += ar[i]
		else:
			ans -= ar[i]
		ans = abs(ans)
	print(1 if ans >= k else 2)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = sum(a)
	if s < k:
		print(2)
		continue
	if k > n:
		print(2)
		continue
	b = a[0]
	for r in range(1, n):
		if r % 2 == 0:
			if b >= 0:
				b = b + a[r]
			else:
				b = b - a[r]
		elif b >= 0:
			b = b - a[r]
		else:
			b = b + a[r]
	if abs(b) >= k:
		print(1)
	else:
		print(2)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	s = sum(arr)
	chance = True
	if s < k:
		print(2)
	else:
		m = 0
		for j in range(n):
			if chance == True:
				if m >= 0:
					m += arr[j]
				else:
					m -= arr[j]
				chance = False
			else:
				if m >= 0:
					m -= arr[j]
				else:
					m += arr[j]
				chance = True
		if abs(m) >= k:
			print(1)
		else:
			print(2)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().strip().split())
	a = list(map(int, input().strip().split()))
	v = 0
	if n % 2 != 0:
		a.append(0)
		n = n + 1
	for j in range(0, n, 2):
		if v >= 0:
			v = v + a[j]
		else:
			v = v - a[j]
		if v >= 0:
			v = v - a[j + 1]
		else:
			v = v + a[j + 1]
	if abs(v) >= k:
		print(1)
	else:
		print(2)


for q in range(int(input())):
	ar = [int(e) for e in input().split()]
	l = [int(e) for e in input().split()]
	c = 0
	for i in range(ar[0]):
		if l[i] == 1:
			if i % 2 == 0:
				if c >= 0:
					c += 1
				else:
					c -= 1
			elif c >= 0:
				c -= 1
			else:
				c += 1
	if abs(c) >= ar[1]:
		print('1')
	else:
		print('2')


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	m = 0
	for i in range(n):
		if i % 2 == 0:
			if m < 0:
				m -= a[i]
			else:
				m += a[i]
		elif m < 0:
			m += a[i]
		else:
			m -= a[i]
	if abs(m) >= k:
		print(1)
	else:
		print(2)


t = int(input())
for i in range(t):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	l = input()
	m = l.split()
	m = list(map(int, m))
	sum = 0
	for j in range(n):
		if sum >= 0:
			sum += m[j] * pow(-1, j)
		else:
			sum += m[j] * pow(-1, j + 1)
	if abs(sum) >= k:
		print(1)
	else:
		print(2)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	flag = 0
	c = 0
	for i in arr:
		if flag % 2 == 0:
			c = abs(c + i)
		else:
			c = abs(c - i)
		flag += 1
	if c < k:
		print(2)
	else:
		print(1)


testCases = int(input())
for Case in range(testCases):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	sum = 0
	for i in range(n):
		if i % 2 == 0:
			if sum > 0:
				if l[i] > 0:
					sum += l[i]
				else:
					sum -= l[i]
			elif l[i] > 0:
				sum -= l[i]
			else:
				sum += l[i]
		elif sum > 0:
			if l[i] > 0:
				sum -= l[i]
			else:
				sum += l[i]
		elif l[i] > 0:
			sum += l[i]
		else:
			sum -= l[i]
	if sum < 0:
		s = -1 * sum
	else:
		s = sum
	if k <= s:
		print(1)
	else:
		print(2)


def soln(n, k, arr):
	res = 0
	for i in range(n):
		if i & 1:
			if abs(k - res) >= abs(-k - res):
				res += arr[i]
			else:
				res -= arr[i]
		elif abs(k - res) >= abs(-k - res):
			res -= arr[i]
		else:
			res += arr[i]
	return 1 if abs(res) >= k else 2
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(soln(n, k, arr))


t = int(input())
for i in range(0, t):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	lst = input().split()
	lst = [int(i) for i in lst]
	sum = 0
	for i in range(0, len(lst)):
		if sum >= 0:
			if i % 2 == 0:
				sum = sum + lst[i]
			else:
				sum = sum - lst[i]
		elif i % 2 == 0:
			sum = sum - lst[i]
		else:
			sum = sum + lst[i]
	if abs(sum) >= k:
		print(1)
	else:
		print(2)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = [int(i) for i in input().split()]
	x = 0
	mauka = 1
	for i in l:
		if i == 0:
			mauka = 1 - mauka
		else:
			if mauka == 1:
				if x >= 0:
					x += 1
				elif x < 0:
					x -= 1
			elif x <= 0:
				x += 1
			else:
				x -= 1
			mauka = 1 - mauka
	print(1 if x >= k else 2)


t = int(input())
for _ in range(t):
	inp = str(input()).split()
	(n, k) = (int(inp[0]), int(inp[1]))
	a = str(input()).split()
	for i in range(len(a)):
		a[i] = int(a[i])
	v = a[0]
	for i in range(1, len(a)):
		if i % 2 == 0:
			if v < 0:
				v -= a[i]
			else:
				v += a[i]
		elif v > 0:
			v -= a[i]
		else:
			v += a[i]
	v = abs(v)
	if v >= k:
		print(1)
	else:
		print(2)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	array = list(map(int, input().split()))
	value = 0
	for i in range(N):
		if i % 2 == 0 and array[i] == 1:
			if value > 0:
				value += 1
			else:
				value -= 1
		elif i % 2 != 0 and array[i] == 1:
			if value > 0:
				value -= 1
			else:
				value += 1
	if abs(value) >= K:
		print(1)
	else:
		print(2)


R = lambda : map(int, input().split())
t = int(input())
while t > 0:
	t = t - 1
	(n, k) = R()
	L = list(R())
	X = 0
	for i in range(n):
		if i % 2:
			if L[i] == 1:
				if X <= 0:
					X += 1
				else:
					X -= 1
		elif L[i] == 1:
			if X >= 0:
				X += 1
			else:
				X -= 1
	if abs(X) >= k:
		print(1)
	else:
		print(2)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	ans = 0
	for i in range(0, n):
		if a[i] == 1 and i % 2 == 0:
			if ans >= 0:
				ans += 1
			else:
				ans -= 1
		elif i % 2 != 0 and a[i] == 1:
			if abs(ans) >= 0:
				if ans <= 0:
					ans += 1
				else:
					ans -= 1
	if abs(ans) >= k:
		print(1)
	else:
		print(2)


import sys, math
from sys import stdin, stdout
mod = int(1000000000.0 + 7)
from collections import deque, defaultdict
from copy import deepcopy
from math import ceil, floor, inf, sqrt, factorial, gcd, log2
ii1 = lambda : int(stdin.readline().strip())
is1 = lambda : stdin.readline().strip()
iia = lambda : list(map(int, stdin.readline().strip().split()))
isa = lambda : stdin.readline().strip().split()
for _ in range(ii1()):
	(n, k) = iia()
	arr = iia()
	s = 0
	for i in range(0, n, 2):
		if s > 0:
			s += arr[i]
		else:
			s -= arr[i]
		if i != n - 1:
			if s > 0:
				s -= arr[i + 1]
			else:
				s += arr[i + 1]
	if abs(s) >= k:
		print(1)
	else:
		print(2)


t = int(input())
while t > 0:
	t -= 1
	(n, k) = [int(x) for x in input().split()]
	seq = [int(x) for x in input().split()]
	V = 0
	for i in range(n):
		if V > 0:
			if i % 2 == 0:
				V += seq[i]
			else:
				V -= seq[i]
		elif i % 2 == 0:
			V -= seq[i]
		else:
			V += seq[i]
	if abs(V) >= k:
		print(1)
	else:
		print(2)


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().strip().split())
	arr = list(map(int, input().strip().split()))
	su = 0
	for i in range(n):
		if i % 2 == 0:
			if abs(su) >= k:
				if su > 0:
					su += arr[i]
				else:
					su -= arr[i]
			elif su > 0:
				su += arr[i]
			else:
				su -= arr[i]
		elif abs(su) >= k:
			if su > 0:
				su -= arr[i]
			else:
				su += arr[i]
		elif su > 0:
			su -= arr[i]
		else:
			su += arr[i]
	if abs(su) >= k:
		print(1)
	else:
		print(2)


import math
import sys
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = 0
	for i in range(n):
		if a[i] == 0:
			continue
		if i % 2 == 0:
			if s >= 0:
				s += 1
			else:
				s -= 1
		elif s < 0:
			s += 1
		else:
			s -= 1
	f = 1 if abs(s) >= k else 2
	print(f)


import math
for _ in range(int(input())):
	(n, k) = [int(j) for j in input().split()]
	l = list(map(int, input().split()))
	sum = l[0]
	for i in range(n - 1):
		if i % 2 == 0:
			if sum >= 0:
				sum -= l[i + 1]
			else:
				sum += l[i + 1]
		elif sum >= 0:
			sum += l[i + 1]
		else:
			sum -= l[i + 1]
	if math.fabs(sum) >= k:
		print('1')
	else:
		print('2')


import math
T = int(input())
for t in range(0, T):
	(N, K) = list(map(int, input().strip().split()))
	binSeq = list(map(int, input().strip().split()))
	addn = 0
	for i in range(0, N):
		if binSeq[i] == 1:
			if addn < 0:
				if i % 2 == 0:
					addn -= 1
				else:
					addn += 1
			elif i % 2 == 0:
				addn += 1
			else:
				addn -= 1
	if abs(addn) >= K:
		print(1)
	else:
		print(2)


for i in range(int(input())):
	a = list(map(int, input().split()))
	n = a[0]
	k = a[1]
	array = list(map(int, input().split()))
	sum = 0
	turn = 1
	if k == 0:
		print(1)
	else:
		for j in range(n):
			if turn == 1 and sum >= 0:
				sum += array[j]
				turn = 2
			elif turn == 2 and sum >= 0:
				sum -= array[j]
				turn = 1
			elif turn == 1 and sum < 0:
				sum -= array[j]
				turn = 2
			elif turn == 2 and sum < 0:
				sum += array[j]
				turn = 1
		if abs(sum) >= k:
			print(1)
		else:
			print(2)


t = int(input())
ans = []
for i in range(t):
	(n, k) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	sums = 0
	chance = 0
	for j in range(n):
		if chance == 0:
			if sums < 0:
				sums -= arr[j]
			else:
				sums += arr[j]
			chance = 1
		else:
			if sums < 0:
				sums += arr[j]
			else:
				sums -= arr[j]
			chance = 0
	if abs(sums) >= k:
		ans.append('1')
	else:
		ans.append('2')
for i in range(t):
	print(ans[i])