Everyone knows that agents in Valorant decide, who will play as attackers, and who will play as defenders. To do that Raze and Breach decided to play $t$ matches of a digit game...

In each of $t$ matches of the digit game, a positive integer is generated. It consists of $n$ digits. The digits of this integer are numerated from $1$ to $n$ from the highest-order digit to the lowest-order digit. After this integer is announced, the match starts.

Agents play in turns. Raze starts. In one turn an agent can choose any unmarked digit and mark it. Raze can choose digits on odd positions, but can not choose digits on even positions. Breach can choose digits on even positions, but can not choose digits on odd positions. The match ends, when there is only one unmarked digit left. If the single last digit is odd, then Raze wins, else Breach wins.

It can be proved, that before the end of the match (for every initial integer with $n$ digits) each agent has an ability to make a turn, i.e. there is at least one unmarked digit, that stands on a position of required parity.

For each of $t$ matches find out, which agent wins, if both of them want to win and play optimally.


-----Input-----

First line of input contains an integer $t$ $(1 \le t \le 100)$  — the number of matches.

The first line of each match description contains an integer $n$ $(1 \le n \le 10^3)$  — the number of digits of the generated number.

The second line of each match description contains an $n$-digit positive integer without leading zeros.


-----Output-----

For each match print $1$, if Raze wins, and $2$, if Breach wins.


-----Example-----
Input
4
1
2
1
3
3
102
4
2069

Output
2
1
1
2



-----Note-----

In the first match no one can make a turn, the only digit left is $2$, it's even, so Breach wins.

In the second match the only digit left is $3$, it's odd, so Raze wins.

In the third match Raze can mark the last digit, after that Breach can only mark $0$. $1$ will be the last digit left, it's odd, so Raze wins.

In the fourth match no matter how Raze plays, Breach can mark $9$, and in the end there will be digit $0$. It's even, so Breach wins.

Difficulty: interview

Starter code:

Solutions:
for _ in range(int(input())):
    n = int(input())
    digits = list(map(int,list(input())))
    if n % 2 == 1:
        containsOdd = False
        for i in range(0,n,2):
            if digits[i] % 2 == 1:
                containsOdd = True
        if containsOdd:
            print(1)
        else:
            print(2)
    else:
        containsEven = False
        for i in range(1,n,2):
            if digits[i] % 2 == 0:
                containsEven = True
        if containsEven:
            print(2)
        else:
            print(1)


q = int(input())
for _ in range(q):
    n = int(input())
    s = input()
    s = list(map(int,s))
    #raze wins if odd
    r = []
    prz = []
    for i in range(n):
        if i%2 == 0:
            r.append(s[i]%2)
        else:
            prz.append(s[i]%2)
    if n%2 == 0:
        if prz.count(0) > 0:
            print(2)
        else:
            print(1)
    else:
        if r.count(1) > 0:
            print(1)
        else:
            print(2)

tests = int(input())
for test in range(tests):
    n = int(input())
    a = [int(i) for i in input()]
    if n % 2 == 0:
        f = False
        for i in range(1, n, 2):
            if a[i] % 2 == 0:
                f = True
                break
        if f:
            print(2)
        else:
            print(1)
    else:
        f = False
        for i in range(0, n, 2):
            if a[i] % 2 == 1:
                f = True
                break
        if f:
            print(1)
        else:
            print(2)
        


t=int(input())
for you in range(t):
    n=int(input())
    s=input()
    if(n%2==0):
        poss=0
        for i in range(1,n,2):
            if(int(s[i])%2==0):
                poss=1
                break
        if(poss):
            print(2)
        else:
            print(1)
    else:
        poss=0
        for i in range(0,n,2):
            if(int(s[i])%2==1):
                poss=1
                break
        if(poss):
            print(1)
        else:
            print(2)


for _ in range(int(input())):
    n = int(input())
    u = list(map(int, list(input())))
    if n % 2 == 0:
        for i in range(1, n, 2):
            if u[i] % 2 == 0:
                print(2)
                break
        else:
            print(1)
    else:
        for i in range(0, n, 2):
            if u[i] % 2 == 1:
                print(1)
                break
        else:
            print(2)


from collections import defaultdict
from queue import deque


def arrinp():
    return [*list(map(int, input().split(' ')))]


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


def intinp():
    return int(input())


def solution():
    n = intinp()
    s = input()
    if n%2 == 0:
        win = 1
        for i in range(n):
            if i%2 == 1:
                if int(s[i])%2 == 0:
                    win = 2
    else:
        win = 2
        for i in range(n):
            if i%2 == 0:
                if int(s[i])%2 == 1:
                    win = 1
    print(win)
    return


testcases = 1
testcases = int(input())
for _ in range(testcases):
    solution()


t = int(input())
for _ in range(t):
    n = int(input())
    s = input()
    if n % 2 == 0:
        for i in range(1, n, 2):
            if int(s[i]) % 2 == 0:
                print(2)
                break
        else:
            print(1)
    else:
        for i in range(0, n, 2):
            if int(s[i]) % 2 == 1:
                print(1)
                break
        else:
            print(2)


import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
# from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var): sys.stdout.write(' '.join(map(str, var)) + '\n')
def out(var): sys.stdout.write(str(var) + '\n')
from decimal import Decimal
# from fractions import Fraction
# sys.setrecursionlimit(100000)
mod = 998244353
INF=float('inf')

for t in range(int(data())):
    n=int(data())
    a=data()
    if n%2==0:
        k=0
        for i in range(1,n,2):
            if int(a[i])%2==0:
                k=1
        if k:
            out(2)
        else:
            out(1)
    else:
        k = 0
        for i in range(0, n, 2):
            if int(a[i]) % 2 == 1:
                k = 1
        if k:
            out(1)
        else:
            out(2)

for _ in range(int(input())):
    n = int(input())
    s = input()

    a = [int(s[i]) for i in range(0, n, 2)]
    b = [int(s[i]) for i in range(1, n, 2)]

    if n % 2 == 0:
        if any(i % 2 == 0 for i in b):
            print(2)
        else:
            print(1)
    else:
        if any(i % 2 == 1 for i in a):
            print(1)
        else:
            print(2)


for _ in range(int(input())):
	n=int(input())
	s=input()
	a1=a2=0
	rayz=s[::2]
	bri=s[1::2]
	if n%2:
		if any(int(i)%2 for i in rayz):print(1)
		else:print(2)
	else:
		if any(int(i)%2==0 for i in bri):print(2)
		else:print(1)

for _ in range(int(input())):
  n=int(input())
  s=input()
  if n%2==1:
    a=[int(i)%2 for i in s[::2]]
    if 1 in a:print(1)
    else:print(2)
  else:
    a=[int(i)%2 for i in s[1::2]]
    if 0 in a:print(2)
    else:print(1)

t=int(input())
for i in range(t):
    n=int(input())
    s=str(input())
    a=len(s)
    if a%2==0:
        x=0
        for j in range(a):
            if j%2==1:
                if int(s[j])%2==0:
                    x+=1
        if x>0:
            print(2)
        else:
            print(1)
    else:
        x=0
        for j in range(a):
            if j%2==0:
                if int(s[j])%2==1:
                    x+=1
        if x>0:
            print(1)
        else:
            print(2)

from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 10 ** 9 + 7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
 
for _ in range(val()):
    n = val()
    s = st()
    
    raze = breach = 0

    for ind, i in enumerate(s):

        num = int(i)
        if ind & 1:
            if num & 1 == 0:breach = 1
        else:
            if num & 1:raze = 1
    
    if n & 1:
        print(1 if raze else 2)
    else:
        print(2 if breach else 1)


import sys
input = sys.stdin.readline


def main():
    t = int(input())
    for _ in range(t):
        N = int(input())
        S = input().strip()

        if N % 2 == 1:
            ans = 2
            for i in range(0, N, 2):
                if int(S[i]) % 2 == 1:
                    ans = 1
            print(ans)
        else:
            ans = 1
            for i in range(1, N, 2):
                if int(S[i]) % 2 == 0:
                    ans = 2
            print(ans)


def __starting_point():
    main()



__starting_point()

import sys
input = sys.stdin.readline

T = int(input())

for t in range(T):
    N = int(input())
    number = str(int(input()))
    if N % 2:
        for i in range(N):
            if i % 2 == 0 and int(number[i]) % 2:
                print(1)
                break
        else:
            print(2)
    else:
        for i in range(N):
            if i % 2 and int(number[i]) % 2 == 0:
                print(2)
                break
        else:
            print(1)


import sys
readline = sys.stdin.readline

T = int(readline())
Ans = [1]*T
for qu in range(T):
    N = int(readline())
    A = list(map(int, readline().strip()))
    Aodd = [A[i]%2 for i in range(N) if not i&1]
    Aeven = [A[i]%2 for i in range(N) if i&1]
    if len(Aodd) == len(Aeven):
        if all(a == 1 for a in Aeven):
            continue
        else:
            Ans[qu] = 2
    else:
        if all(a == 0 for a in Aodd):
            Ans[qu] = 2

print('\n'.join(map(str, Ans)))

import math,sys
from sys import stdin,stdout
from collections import Counter, defaultdict, deque
input = stdin.readline
I = lambda:int(input())
li = lambda:list(map(int,input().split()))

def solve():
    n=I()
    s=input().strip()
    if(n%2):
        f=2
        for i in range(0,n,2):
            if(int(s[i])%2):
                f=1
        print(f)
    else:
        f=1
        for i in range(1,n,2):
            if(int(s[i])%2==0):
                f=2
        print(f)

for _ in range(I()):
    solve()

#!/usr/bin/env python3
import sys
input = sys.stdin.readline

t = int(input())

for _ in range(t):
    n = int(input())
    s = input().rstrip()
    if len(s) % 2 == 0:
        ben_wins = False
        for ch in s[1::2]:
            if int(ch) % 2 == 0:
                ben_wins = True
    else:
        ben_wins = True
        for ch in s[0::2]:
            if int(ch) % 2 == 1:
                ben_wins = False
    
    if ben_wins:
        print(2)
    else:
        print(1)

t = int(input())
for _ in range(t):
    n = int(input())
    s = str(input())
    R = []
    B = []
    for i in range(n):
        t = int(s[i])
        t %= 2
        if i%2 == 0:
            R.append(t)
        else:
            B.append(t)
    R = set(R)
    B = set(B)
    if n%2 == 1:
        if 1 in R:
            print(1)
        else:
            print(2)
    else:
        if 0 in B:
            print(2)
        else:
            print(1)


for _ in range(int(input())):
    n = int(input())
    digits=[int(c) for c in input()]
    ans = None
    if n&1:
        ##if n is odd
        for i in range(0,n,2):
            if digits[i]&1:
                ans = True
                break
        else:
            ans = False
    else:
        for i in range(1,n,2):
            if digits[i]%2 == 0:
                ans = False
                break
        else:
            ans = True
    
    print(1 if ans else 2)

for i in range (int(input())):
    n=int(input())
    s=input()
    odd=0
    even=0
    for i in range (0,n,2):
        if int(s[i])%2==1:
            odd+=1
    for i in range (1,n,2):
        if int(s[i])%2==0:
            even+=1
    if n%2==1:
        if odd>0:
            print(1)
        else:
            print(2)
    else:
        if even>0:
            print(2)
        else:
            print(1)

def a(l):
    odd = 0
    even = 0
    for x in l:
        if x % 2 == 1:
            odd += 1
        else:
            even += 1
    return (odd, even)

T = int(input())
for _ in range(T):
    n = int(input())
    l = list(map(int, list(input())))
    odds = l[::2]
    evens = l[1::2]
    if n % 2 == 1:
        x,y = a(odds)
        print(1 if x > 0 else 2)
    else:
        x,y = a(evens)
        print(2 if y > 0 else 1)


t = int(input())

for _ in range(t):
    n = int(input())
    s = [int(x) for x in input()]
    A = s[0::2] 
    B = s[1::2] 
    if n%2 == 0:
        if any(x%2 == 0 for x in B):
            print(2)
        else:
            print(1)
    else:
        if any(x%2 == 1 for x in A):
            print(1)
        else:
            print(2)




t=int(input())
while t:
    t-=1
    n=int(input())
    a=input()
    if n%2==0:
        flag=0
        for i in range(1,n,2):
            if int(a[i])%2==0:
                flag+=1
                break
        if flag:
            print(2)
        else:
            print(1)
    else:
        flag=0
        for i in range(0,n,2):
            if int(a[i])%2==1:
                flag+=1
                break
        if flag:
            print(1)
        else:
            print(2)


for t in range(int(input())):
    n = int(input())
    d = [int(i) for i in input()]
    if n % 2 == 1:
        #evens go for odds
        if 1 in [d[i] % 2 for i in range(0, n, 2)]:
            print(1)
        else:
            print(2)
    else:

        if 0 in [d[i] % 2 for i in range(1, n, 2)]:
            print(2)
        else:
            print(1)


def main():
    n = int(input())
    lst = input()
    if n % 2 == 0:
        for i in range(1, n, 2):
            if int(lst[i]) % 2 == 0:
                print("2")
                return
        print("1")
        return
    for i in range(0, n, 2):
        if int(lst[i]) % 2 == 1:
            print("1")
            return
    print("2")
    return


def __starting_point():
    t = int(input())
    for i in range(t):
        main()
__starting_point()