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 ≤ t ≤ 100) — the number of matches.

The first line of each match description contains an integer n (1 ≤ n ≤ 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.

import java.io.BufferedReader;
import java.text.DecimalFormat;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.Date;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.io.*;

public class abc {
	static PrintWriter pw;

	static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}

	}

	public static int gcd(int a, int b) {
		return b == 0 ? a : gcd(b, a % b);
	}

	public static boolean isPrime(long n) {
		if (n == 2)
			return true;
		long i = 2;
		while (i * i <= n) {
			if (n % i == 0)
				return false;
			i++;
		}
		return true;
	}

	public static long[] remove(long n) {
		long res[] = new long[1000000000];
		long rese = 0;
		int i = 0;
		while (n > 0) {
			long dig = n % 10;
			n = n / 10;
			if (dig > 0) {
				rese = dig;
				res[i++] = rese;
			}
		}
		return res;
	}

	static int ceil(int x, int y) {
		return (x % y == 0 ? x / y : (x / y + 1));
	}

	static long ceil(long x, long y) {
		return (x % y == 0 ? x / y : (x / y + 1));
	}

	static int max(int x, int y) {
		return Math.max(x, y);
	}

	static int min(int x, int y) {
		return Math.min(x, y);
	}

	static int abs(int x) {
		return Math.abs(x);
	}

	static long abs(long x) {
		return Math.abs(x);
	}

	static int log2(int N) {
		int result = (int) (Math.log(N) / Math.log(2));
		return result;
	}

	static long max(long x, long y) {
		return Math.max(x, y);
	}

	static long min(long x, long y) {
		return Math.min(x, y);
	}

	public static class pair {
		int x;
		int y;

		public pair(int a, int b) {
			x = a;
			y = b;
		}
	}

	public static class Comp implements Comparator<pair> {
		public int compare(pair a, pair b) {
			if (a.x != b.x) {
				return a.x - b.x;
			} else {
				return a.y - b.y;
			}
		}
	}

	public static void extract(ArrayList<Integer> ar, int k, int d) {
		int c = 0;
		for (int i = 1; i < k; i++) {
			int x = 0;
			boolean dm = false;
			while (x > 0) {
				long dig = x % 10;
				x = x / 10;
				if (dig == d) {
					dm = true;
					break;
				}
			}
			if (dm)
				ar.add(i);
		}
	}

	public static void dfs(int index, boolean vis[], int a[], int b[], int n) {
		vis[index] = true;
		for (int i = 0; i < n; i++) {
			if (!vis[i] && (a[i] == a[index] || b[i] == b[index]))
				dfs(i, vis, a, b, n);
		}
	}

	public static int countSetBitsUtil(int x) {
		if (x <= 0)
			return 0;
		return (x % 2 == 0 ? 0 : 1) + countSetBitsUtil(x / 2);
	}

	public static double decimalPlaces(double sum) {
		DecimalFormat df = new DecimalFormat("#.00");
		String angleFormated = df.format(sum);
		double fin = Double.parseDouble(angleFormated);
		return fin;
	}
//use collections.swap for swapping 
	static boolean isSubSequence(String str1, String str2, int m, int n) {
		int j = 0;

		for (int i = 0; i < n && j < m; i++)
			if (str1.charAt(j) == str2.charAt(i))
				j++;

		return (j == m);
	}
	
	static long[] sum(int k,long n )
	{
		long a[]=new long[k];
		int c=0;
		while(n>0)
		{
			a[c++]=n%10;
			n=n/10;
		}
		return a;
	}
	static long pow(long base, long power)
	{
		if (power == 0) {
	        return 1;
	    }
	     long result = pow(base,power/2);
	    if (power%2 == 1) {
	        return result*result*base;
	    }
	    return result*result;
	}
	public static void main(String[] args) throws Exception {

		FastReader sc = new FastReader();
		pw = new PrintWriter(System.out);
		int t=sc.nextInt();
		while(t-->0)
		{
			int n=sc.nextInt();
			String s=sc.nextLine();
			long a[]=new long[n];
			for(int i=0;i<n;i++)
			{
				String st=Character.toString(s.charAt(i));
				int k=Integer.parseInt(st);
				a[i]=k;
			}
			int f=0;
			if(n%2==1)
			{
				for(int i=0;i<n;i+=2 )
				{
					if(a[i]%2==1)
					{
						f=-1;
						break;
					}
				}
				if(f==-1)
					pw.println("1");
				else
					pw.println("2");
			}
			else
			{
				for(int i=1;i<n;i+=2 )
				{
					if(a[i]%2==0)
					{
						f=-1;
						break;
					}
				}
				if(f==-1)
					pw.println("2");
				else
					pw.println("1");
			}
			
		}
		
		pw.flush();
	}
}
