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.math.BigInteger;
	import java.sql.Array;
	import java.util.ArrayList;
		import java.util.Arrays;
		import java.util.Collection;
		import java.util.Collections;
		import java.util.Comparator;
		import java.util.HashMap;
		import java.util.InputMismatchException;
		import java.util.Iterator;
		import java.util.LinkedHashSet;
		import java.util.LinkedList;
		import java.util.List;
		import java.util.Map;
		import java.util.Map.Entry;
		import java.util.PriorityQueue;
		import java.util.Queue;
		import java.util.Scanner;
		import java.util.Set;
		import java.util.Stack;
		import java.io.BufferedReader;
		import java.io.IOException;
		import java.io.InputStream;
		import java.io.InputStreamReader;
		import java.util.Scanner;
		import java.util.StringTokenizer;
		import java.util.TreeMap;
		import java.util.TreeSet;
		
		public class Main {
											
		//	static FastReader sc= new FastReader();
		static ArrayList<Integer> C;
		static ArrayList<Integer> B;
		static	int mod=(int)1e9+9;
		static long dp[];
		static int k;
		
		static StringBuilder as=new StringBuilder();
		static InputReader rd=new InputReader(System.in);
		
		static int count=0;
	
		public static void main(String[] args) {
	
			
			int t=rd.readInt();
			while(t-->0) {
				
				int n=rd.readInt();
				
				String s=rd.readString();
				
				int o=0;
				
				if(n%2!=0) {
				for(int i=0;i<n;i+=2) {
					
					if((s.charAt(i)-48)%2==0) {
						o++;
					}
					
					
					
				}
				
				if(o<=n/2)System.out.println(1);
				else System.out.println(2);
				
				}
				
				
			
			if(n%2==0) {
				for(int i=1;i<n;i+=2) {
					
					if((s.charAt(i)-48)%2!=0) {
						o++;
					}
					
					
					
				}
				
				if(o<n/2)System.out.println(2);
				else System.out.println(1);
				}
				
				
			}
			
		}
		
		class Solver{
			
			
			int val;int index;
			public Solver(int val,int index) {
				// TODO Auto-generated constructor stub
				this.val=val;
				this.index=index;
			
			}
		}
		
			static void DFS(ArrayList<ArrayList<Integer>> adj,int s,boolean[] visited) {
				
				
				
				count++;
			//	System.out.println(count);
				visited[s]=true;
				
				for(int i:adj.get(s)) {
					
					if(!visited[i])DFS(adj, i, visited);
				}
				
				
				
			}
	
		
			void BFS(int s,int n) {
				
				
				boolean visited[]= new boolean[n];
				
				LinkedList<Integer> q=new LinkedList<>();
				
				
				
				
			}
				    
				    
				    
				    
				
		
		
		
		static int MSB(int z) {
			for (int i=20; i>=0; i--) {
				if (((z>>i)&1)!=0) return i;
			}
			return -1;
		}
	
		
		static long ans=(long)1e18;
		static void dfs(int s,ArrayList<ArrayList<Integer>> adj,boolean []visited) {
			
			
			visited[s]=true;
			
			
			for(int i:adj.get(s)) {
				
				if(!visited[i])dfs(i, adj, visited);
			}
			
			
			
			
		}
		
		
		
		
		
		
		static boolean isPowerOfTwo (int x) 
		{ 
		  /* First x in the below expression is  
		    for the case when x is 0 */
		    return x!=0 && ((x&(x-1)) == 0); 
		      
		} 
		
				
				//extended Euclidean Algorithm 
				public static int gcd(int a, int b) 
				{ 
				    if (a == 0) 
				        return b; 
				      
				    return gcd(b%a, a); 
				} 
		
		
		static boolean isPrime(int n) { 
		    //check if n is a multiple of 2 
		    if (n%2==0) return false; 
		    //if not, then just check the odds 
		    for(int i=3;i<=Math.sqrt(n);i+=2) { 
		        if(n%i==0) 
		            return false; 
		    } 
		    return true; 
		} 
					static long solve(long n) {
						long sum=(n*(n+1)/2);
						long l=sum/2;
						if(n==3) {
							return 2;
						}
						long k=n;
						if(sum%2==0) {
							long j=n;
							int c=1;
							boolean flag=false;
							long s=0;
							while(j<l) {
								
								n--;
								c++;
								j+=n;
								
								if(j==l) {flag =true;s=n-1;}
								
							}
							long point =l-(j-k);
							long e=0;
							
							if(flag) {
								e=s*(s-1)/2+(k-s)*(k-s-1)/2;
								
							}
							
						//System.out.println(e+" "+c);
							return (c+e);
						}
						else return 0;
						
						
						
					
						
					}
			
			
			static class solver{
				int d;
				double w;
				public solver(int d,double w) {
					
				this.d=d;
				this.w=w;
				
					
				}
				
				
			}
			
			
			
			
			
			
			  static class InputReader {
			        private InputStream stream;
			        private byte[] buf = new byte[1024];
			        private int curChar;
			        private int numChars;
			        private SpaceCharFilter filter;
		
			        public InputReader(InputStream stream) {
			            this.stream = stream;
			        }
		
			        public int read() {
			            if (numChars == -1)
			                throw new InputMismatchException();
			            if (curChar >= numChars) {
			                curChar = 0;
			                try {
			                    numChars = stream.read(buf);
			                } catch (IOException e) {
			                    throw new InputMismatchException();
			                }
			                if (numChars <= 0)
			                    return -1;
			            }
			            return buf[curChar++];
			        }
		
			        public int readInt() {
			            int c = read();
			            while (isSpaceChar(c))
			                c = read();
			            int sgn = 1;
			            if (c == '-') {
		    sgn = -1;
		    c = read();
		}
		int res = 0;
		do {
		    if (c < '0' || c > '9')
		        throw new InputMismatchException();
		    res *= 10;
		    res += c - '0';
		        c = read();
		    } while (!isSpaceChar(c));
		    return res * sgn;
		}
		
		public String readString() {
		    int c = read();
		    while (isSpaceChar(c))
		        c = read();
		    StringBuilder res = new StringBuilder();
		    do {
		        res.appendCodePoint(c);
		        c = read();
		    } while (!isSpaceChar(c));
		    return res.toString();
		}
		
		public boolean isSpaceChar(int c) {
		    if (filter != null)
		        return filter.isSpaceChar(c);
		    return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
			        }
		
			        public String next() {
			            return readString();
			        }
		
			    }
			
			  public interface SpaceCharFilter {
			        public boolean isSpaceChar(int ch);
			    }	
			
			
			static int c=0;
		static    void DFSUtil(int s,ArrayList<ArrayList<solver>> adj,int V,boolean visited[],double pw) {
		    	
			
		    	visited[s]=true;
		    	c++;
		    	
		  // 	System.out.print(c+" ");
		
		for(solver i:adj.get(s)) {
			
		
		if(pw>i.w) {
			//System.out.println(pw+" "+i.w+" "+(pw>i.w));
		    		continue;}
		    		
		    		if(!visited[i.d]) {
		    			
		    			DFSUtil(i.d,adj,V,visited,i.w);
		    		}
		    		
		    	}
		    	
		    }
		    
			
			public static <T> ArrayList<T> removeDuplicates(ArrayList<T> list) 
		    { 
		  
		        // Create a new LinkedHashSet 
		        Set<T> set = new LinkedHashSet<>(); 
		  
		        // Add the elements to set 
		        set.addAll(list); 
		  
		        // Clear the list 
		        list.clear(); 
		  
		        // add the elements of set 
		// with no duplicates to the list 
		        list.addAll(set); 
		  
		        // return the list 
				        return list; 
				    } 
		static		class Ungraph{
					
					
					int V,E;
					
					Edge edge[];
					
					class Edge{
						int src,dest;
						
					};
					
						public Ungraph(int v,int e) {
							// TODO Auto-generated constructor stub
		
		V=v;
		
		E=e;
		edge=new Edge[e];
		
		for(int i=0;i<e;i++) {
			edge[i]=new Edge();
			
		}
		
		
		}
		
		class subset{
			
			int parent;
			int rank;
			
		}
		
		int find(subset subsets[],int i) {
			
			if(subsets[i].parent!=i) {
				subsets[i].parent=find(subsets,subsets[i].parent);
			}
			return subsets[i].parent;
		}
		
		
		//finding union
													void Union(subset subsets[],int x,int y) {
														int xroot=find(subsets,x);
														int yroot=find(subsets,y);
														
														if(subsets[xroot].rank<subsets[yroot].rank)subsets[xroot].parent=yroot;
														if(subsets[xroot].rank<subsets[yroot].rank)subsets[yroot].parent=xroot;
														 else
														    { 
														        subsets[xroot].parent = yroot; 
														        subsets[yroot].rank++; 
														    } 
													}
													
													
													  
													
													
													int isCycle(Ungraph graph) {
														
														subset subsets[]=new subset [graph.V];
														
															for(int i=0;i<graph.V;i++) { 	
																 subsets[i] = new subset(); 
																 subsets[i].parent=i;
																 subsets[i].rank=0;
																
															}
															for(int i=0;i<graph.E;i++) {
																int x=find(subsets,graph.edge[i].src);
																int y=find(subsets,graph.edge[i].dest);
																if(x==y)return 1;
																graph.Union(subsets, x, y);
															}
														
														return 0;
														
														
													}
													
												
												
											}
												
												
												
											
												
												
												
												
												
												
												
												
												
									
		}
		    