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.PrintWriter;
import java.util.StringTokenizer;


public class MinMexCut {

	//2d arraylist adj list
	//ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>();
	//for (int i = 0; i < n; i++)adj.add(new ArrayList<Integer>());
	/*
	 -Binary search
	 int lo = 0;
	 int hi = highest val possible;
	 while (lo <= hi){
	 int mid = (lo+hi)/2;
	 
	 if (check){
	 
	 	}else {
	 	
	 	}
	 }
	 */
		
		
		
	//Custom Comparators
	/*
	 //ArrayList<comp> a = new ArrayList<comp>();
	 //long [] a = new new long [n];
	 
	 class comp implements Comparable<comp> {

		public int a, b;

		public comp(int a, int b) {
			this.a = a;
			this.b = b;
		}

		public int compareTo(comp other) {
		//sort by 1 criteria
		 //return Integer.compare(this.a. other.a);
		  
		  //sort by 2 criteria
			//if (this.a != other.a) {
			//	return Integer.compare(this.a, other.a);
			//} else {
				return Integer.compare(other.b, this.b);
			//}
		}
	}
	 */
		
		
		
	//MultiSet
	/*
	 static void add(int x){
		if(multiset.containsKey(x)){
			multiset.put(x, multiset.get(x) + 1);
		} else {
			multiset.put(x, 1);
		}
	}

	static void remove(int x){
		multiset.put(x, multiset.get(x) - 1);
		if(multiset.get(x) == 0){
			multiset.remove(x);
		}
	}
	 */
	 
		
	//DFS and other related items
	//ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>();
	//for (int i = 0; i < n; i++)adj.add(new ArrayList<Integer>());
	//boolean [] visited = new boolean [n];
	/*
	 static void dfs(int node) {
			if (visited[node]) return;
			
			nodes++;
			visited[node] = true;
			for (int neighbor : adj.get(node)) {
				dfs(neighbor);
			}
	 */
	 

		
	//Floodfill
	/*
	 static void floodfill(int r, int c, char curC) {
		if (r < x || r >= 0 || c < y || c >= 0) {
			return;
		} 
		if(visited[r][c] || grid[r][c] != curC) {
			return;
		}
		visited[r][c] = true;
		size++;
		
		floodfill(r+1, c, curC);
		floodfill(r-1, c, curC);
		floodfill(r, c+1, curC);
		floodfill(r, c-1, curC);
	}
	 */
		
		
	//2 pointers
	/*
	 int l = 0, r = 0, cur = 0, ans = 0;
			while (l < n && r < n) {
				while (r < n) {
					r++;
					if ((check condition)) {
						r--;
						break;
					}
				}

				l++;
			}
	 */
		
		
	//mod int template
		/*static int mod(int a, int m)
	{
	    return (a%m + m) % m;
	}*/
		
		
		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) throws IOException {
			PrintWriter out = new PrintWriter(System.out);
			FastReader in = new FastReader();
			 int t = in.nextInt();

			 for (int ie = 0; ie < t; ie++) {
			
			 
			 String s = in.next();
			 if (!s.contains("1")) {
				 out.println(1);
				 continue;
			 }
			 if (!s.contains("0")) {
				 out.println(0);
				 continue;
			 }
			 int z = 0;
			 for (int i = 0; i < s.length(); i++) {
				 if (s.charAt(i) == '0') {
					 z++;
				 }
			 }
			 out.println(Math.min(z, 2));
			 }
			 out.close();

	}

}
