A binary string is a string that consists of characters 0 and 1.

Let \operatorname{MEX} of a binary string be the smallest digit among 0, 1, or 2 that does not occur in the string. For example, \operatorname{MEX} of 001011 is 2, because 0 and 1 occur in the string at least once, \operatorname{MEX} of 1111 is 0, because 0 and 2 do not occur in the string and 0 < 2.

A binary string s is given. You should cut it into any number of substrings such that each character is in exactly one substring. It is possible to cut the string into a single substring — the whole string.

A string a is a substring of a string b if a can be obtained from b by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

What is the minimal sum of \operatorname{MEX} of all substrings pieces can be?

Input

The input consists of multiple test cases. The first line contains a single integer t (1 ≤ t ≤ 10^4) — the number of test cases. Description of the test cases follows.

Each test case contains a single binary string s (1 ≤ |s| ≤ 10^5).

It's guaranteed that the sum of lengths of s over all test cases does not exceed 10^5.

Output

For each test case print a single integer — the minimal sum of \operatorname{MEX} of all substrings that it is possible to get by cutting s optimally.

Example

Input


6
01
1111
01100
101
0000
01010


Output


1
0
2
1
1
2

Note

In the first test case the minimal sum is \operatorname{MEX}(0) + \operatorname{MEX}(1) = 1 + 0 = 1.

In the second test case the minimal sum is \operatorname{MEX}(1111) = 0.

In the third test case the minimal sum is \operatorname{MEX}(01100) = 2.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.StringTokenizer;

//import graph_representation.pair1;

//import dynamic_programming.FastReader;
public class hacker{
	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 void main(String[] args) {
		OutputStream outputStream =System.out;
	    PrintWriter out =new PrintWriter(outputStream);
	FastReader s=new FastReader();	
	int t=s.nextInt();
	while(t>0) {
		int c=0;
		int d=0;
		int ans=0;
		int c1=0;
		int c2=0;
		String str=s.next();
		int n=str.length();
		for(int i=0;i<n;i++) {
			if(str.charAt(i)=='0') {
	             c=1;
	             c1=1;
			}else {
				d+=c;
				c=0;
				c2=1;
			}
		}
		if(c==1)d++;
		if(c1==1 && c2==1) {
			ans=2;
		}else if(c1==1) {
			ans=1;
		}else {
			ans=0;
		}
		
		out.println(Math.min(d, ans));
		t--;
	}
	out.close();
		}
	
	static boolean JOHNSONS_ALGO(int n,pair[] edges,int m){
		boolean p=bellman_ford(2001,edges,n,m);
		if(!p) {
			System.out.println("Not Possible");
			return true;
		}else {
			for(int i=1;i<=n;i++) {
				int g=f[i].size();
				for(int j=0;j<g;j++) {
					int b1=f[i].get(j).b;
					f[i].get(j).w=(int) (f[i].get(j).w+dist[i]-dist[b1]);
				}
			}
			for(int i=1;i<=n;i++) {
				Dijktras_algo(i);
			}
		}
//		for(int i=1;i<=n;i++) {
////			for(int j=0;j<f[i].size();j++) {
////				System.out.print(f[i].get(j).w+" ");
////			}
//			System.out.println(dist[i]);
//		}
		return false;
	}
	static long[] dist=new long[2002];
	static boolean bellman_ford(int node,pair[] edges,int n,int m) {
		for(int i=1;i<=n;i++) {
			dist[i]=Integer.MAX_VALUE;
		}
		dist[node]=0;
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=m;j++) {
				int u=edges[j].a;
				int v=edges[j].b;
				int w=edges[j].w;
//				System.out.println(u+" "+v+" "+w);
				if(i!=n) {
				if(dist[u]!=Integer.MAX_VALUE) {
					dist[v]=Math.min(dist[u]+w, dist[v]);
				}
				}else {
				if(dist[v]>dist[u]+w) {
					return false;
				}
				}
			}
		}
		return true;
		
	}
	static void Dijktras_algo(int node) {
		PriorityQueue<pair1> q=new PriorityQueue<>();
		dist1[node][node]=0;
		q.add(new pair1(node,0));
//		System.out.println(node);
		while(!q.isEmpty()) {
			pair1 pq=q.poll();
//			System.out.println(node);
			int b1=pq.b;
			int w1=pq.w;
			int g=f[b1].size();
			if(vis[node][b1]) {
				continue;
			}
			vis[node][b1]=true;
			for(int i=0;i<g;i++) {
				if(dist1[node][f[b1].get(i).b]>w1+f[b1].get(i).w) {
					q.add(new pair1(f[b1].get(i).b,f[b1].get(i).w+w1));
					dist1[node][f[b1].get(i).b]=f[b1].get(i).w+w1;
				}
			}
		}
	}
	static class pair{
		private int a;
		private int b;
		private int w;
		pair(int a,int b,int w){
			this.a=a;
			this.b=b;
			this.w=w;
		}
	}
	static boolean[][] vis=new boolean[2002][2002];
	static ArrayList<pair1>[] f=new ArrayList[2002];
	static int[][] dist1=new int[2002][2002];
	static class pair1 implements Comparable<pair1>{
		private int b;
		private int w;
		pair1(int b,int w){
			this.b=b;
			this.w=w;
		}
		public int compareTo(pair1 o) {
			return this.w-o.w;
			
		}
	}
}