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

Starter code:

Solutions:
# cook your dish here
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]
  else:
   if m<0:
    m+=a[i]
   else:
    m-=a[i]
 if abs(m)>=k:
  print(1)
 else:
  print(2)
   


# cook your dish here
for _ in range(int(input())):
 n,k=list(map(int, input().split()))
 l=list(map(int, input().split()))
 
 v=0
 for i in range(n):
  if i%2==0:
   if v<0:
    v-=l[i]
    
   else:
    v+=l[i]
    
  else:
   if v<0:
    v+=l[i]
    
   else:
    v-=l[i]
  
 if abs(v)>=k:
  print('1')
  
 else:
  print('2')

# cook your dish here
for _ in range(int(input())):
 n,k=list(map(int,input().split()))
 l=list(map(int,input().split()))
 s=0
 for i in range(n):
  if i%2==0:
   if s>0:
    s+=l[i]
   else:
    s-=l[i]
  else:
   if s>0:
    s-=l[i]
   else:
    s+=l[i]
 if abs(s)>=k:
  print('1')
 else:
  print('2')
 


# cook your dish here
for u in range(int(input())):
 n,k=list(map(int,input().split()))
 l=list(map(int,input().split()))
 s=0
 for i in range(n):
  if(i%2==0):
   if(s>=0):
    s+=l[i]
   else:
    s-=l[i]
  else:
   if(s>=0):
    s-=l[i]
   else:
    s+=l[i]
 if(abs(s)>=k):
  print(1)
 else:
  print(2)


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]
   else:
    if l[i]>0:
     sum-=l[i]
    else:
     sum+=l[i]
  else:
   if sum>0:
    if l[i]>0:
     sum-=l[i]
    else:
     sum+=l[i]
   else:
    if l[i]>0:
     sum+=l[i]
    else:
     sum-=l[i]
 #print('sum',sum)
 if sum<0:
  s=(-1)*sum
 else:
  s=sum
 if k<=s:
  print(1)
 else:
  print(2)


for _ in range(int(input())):
 n,k=list(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]
  else:
   if x>=0:
    x-=l[i]
   else:
    x+=l[i]
 if abs(x)>=k:
  print(1)
 else:
  print(2)


t=int(input())
for j in range(t):
 n,k=list(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)


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

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
  else:
   if v>=0:
    v-=i
   else:
    v+=i
 if abs(v)>=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
  else:
   if v>=0:
    v-=i
   else:
    v+=i
 if abs(v)>=k:
  print(1)
 else:
  print(2)

# cook your dish here
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]
  else:
   if(c<0):
    c+=x[i]
   else:
    c-=x[i]
 if(abs(c)>=k):
  print(1)
 else:
  print(2)

for j in range(int(input())):
 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]
  else:
   if(c<0):
    c+=x[i]
   else:
    c-=x[i]
 if(abs(c)>=k):
  print(1)
 else:
  print(2)

for j in range(int(input())):
 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]
  else:
   if(c<0):
    c+=x[i]
   else:
    c-=x[i]
 if(abs(c)>=k):
  print(1)
 else:
  print(2)

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))
  else:
   if(turn==0):    #vanja's turn
    if(K - abs(value + 1) <= K - abs(value-1)):
     value+=1
     turn=1
    else:
     value-=1
     turn=1
   else:           #miksi's turn
    if(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)

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]
  else:
   if sum >= 0:
    sum += s[i + 1]
   else:
    sum -= s[i + 1]
 if math.fabs(sum) >= K:
  print("1")
 else:
  print("2")


# cook your dish here
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]
  else:
   if sum>=0:
    sum+=l[i+1]
   else:
    sum-=l[i+1]
 if math.fabs(sum)>=k:
  print("1")
 else:
  print("2")


# cook your dish here
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]
    
  else:
   if 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))


# cook your dish here
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]
   
  else:
   if 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))

# cook your dish here
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]
   
  else:
   if 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))

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)

# cook your dish here
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 _ 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)


# cook your dish here
t = int(input())

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