Consider a simplified penalty phase at the end of a football match.

A penalty phase consists of at most 10 kicks, the first team takes the first kick, the second team takes the second kick, then the first team takes the third kick, and so on. The team that scores more goals wins; if both teams score the same number of goals, the game results in a tie (note that it goes against the usual football rules). The penalty phase is stopped if one team has scored more goals than the other team could reach with all of its remaining kicks. For example, if after the 7-th kick the first team has scored 1 goal, and the second team has scored 3 goals, the penalty phase ends — the first team cannot reach 3 goals.

You know which player will be taking each kick, so you have your predictions for each of the 10 kicks. These predictions are represented by a string s consisting of 10 characters. Each character can either be 1, 0, or ?. This string represents your predictions in the following way:

  * if s_i is 1, then the i-th kick will definitely score a goal; 
  * if s_i is 0, then the i-th kick definitely won't score a goal; 
  * if s_i is ?, then the i-th kick could go either way. 



Based on your predictions, you have to calculate the minimum possible number of kicks there can be in the penalty phase (that means, the earliest moment when the penalty phase is stopped, considering all possible ways it could go). Note that the referee doesn't take into account any predictions when deciding to stop the penalty phase — you may know that some kick will/won't be scored, but the referee doesn't.

Input

The first line contains one integer t (1 ≤ t ≤ 1 000) — the number of test cases.

Each test case is represented by one line containing the string s, consisting of exactly 10 characters. Each character is either 1, 0, or ?.

Output

For each test case, print one integer — the minimum possible number of kicks in the penalty phase.

Example

Input


4
1?0???1001
1111111111
??????????
0100000000


Output


7
10
6
9

Note

Consider the example test:

In the first test case, consider the situation when the 1-st, 5-th and 7-th kicks score goals, and kicks 2, 3, 4 and 6 are unsuccessful. Then the current number of goals for the first team is 3, for the second team is 0, and the referee sees that the second team can score at most 2 goals in the remaining kicks. So the penalty phase can be stopped after the 7-th kick.

In the second test case, the penalty phase won't be stopped until all 10 kicks are finished.

In the third test case, if the first team doesn't score any of its three first kicks and the second team scores all of its three first kicks, then after the 6-th kick, the first team has scored 0 goals and the second team has scored 3 goals, and the referee sees that the first team can score at most 2 goals in the remaining kicks. So, the penalty phase can be stopped after the 6-th kick.

In the fourth test case, even though you can predict the whole penalty phase, the referee understands that the phase should be ended only after the 9-th kick.
		/*
		TO LEARN
		1-segment trees
		2-euler tour
		3-fenwick tree and interval tree
		*/
		/*
		TO SOLVE 
		uva 1103
		codeforces 722 kavi on pairing duty
		*/
		/*
		bit manipulation shit
		1-Computer Systems: A Programmer's Perspective
		2-hacker's delight
		3-(02-03-bits-ints)
		4-machine-basics
		5-Bits Manipulation tutorialspoint
		*/
		/*
		TO WATCH
		1-what is bitmasking by kartik arora youtube

		*/
		            import java.util.*;
				    import java.math.*;
				    import java.io.*; 
				    import java.util.stream.Collectors;

				       public class A{
				     
				  static InputStream inputStream = System.in;
		            static FastScanner scan=new FastScanner();
				     public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
static String s;
static int dp[][][];
static int rec(int i,int first,int second)
{
	if(i==11)
		return i-1;
	
	if(first>second){
		int ff;
		if(i%2==0)
			ff=i;
		else ff=i+1;
		int cnt=0;
		while(ff<=10)
		{
			ff+=2;
			cnt++;
		}
		if(second+cnt<first){
			//out.println(cnt+" "+first+" "+i+" ");
			return i-1;
		}
	}
	if(second>first){
	int ff;
		if(i%2==1)
			ff=i;
		else ff=i+1;
		int cnt=0;
		while(ff<=10)
		{
			ff+=2;
			cnt++;
		}
			if(first+cnt<second)
			return i-1;
	}
	if(dp[i][first][second]!=-1)
		return dp[i][first][second];
	int min=20;
	if(s.charAt(i)=='1')
	{
		if(i%2==1)
			min=rec(i+1,first+1,second);
		else min=rec(i+1,first,second+1);
	}
	else if(s.charAt(i)=='0')
	{
		//if()
			if(i%2==1)
			min=rec(i+1,first,second);
		else min=rec(i+1,first,second);
	}
	else 
	{
		if(i%2==1)
		 min=Math.min(rec(i+1,first+1,second),rec(i+1,first,second));
		else min=Math.min(rec(i+1,first,second+1),rec(i+1,first,second));
	}
	return dp[i][first][second]=min;
}
			public static void main(String[] args)  throws Exception 
		      {
			
				//	scan=new FastScanner("help.in");
				//out = new PrintWriter("lifeguards.out");
				 
				 /*
				 currently doing 
				 1-digit dp
				 2-ds like fenwick and interval tree and sparse table 
				 */
				 /*
				 READING 
				 1-Everything About Dynamic Programming codeforces
				 2-DYNAMIC PROGRAMMING: FROM NOVICE TO ADVANCED topcoder
				 3-Introduction to DP with Bitmasking codefoces
				 4-Bit Manipulation hackerearth
				 5-read more about mobious and inculsion-exclusion 
				 */
			//	System.out.println(1&(4>>2));
			//	System.out.println(4&(1<<2));



				    int tt=1;
				tt=scan.nextInt();

			 outer:while(tt-->0)
				    {	

s=scan.next();
s=" "+s;
dp=new int[11][11][11];
for(int KK[][]:dp)
for(int K[]:KK)
	Arrays.fill(K,-1);
out.println(rec(1,0,0));



				    	
		}
		   out.close();
	}
	static class DSU
	{
		int parent[];
		int size[];
		DSU(int n)
		{
			parent=new int[n+10];
			size=new int[n+10];
			for(int i=0;i<n+10;i++){
				parent[i]=i;
				size[i]=1;
			}
		}
		 int find(int x){
			if(x==parent[x])
				return x;
			return parent[x]=find(parent[x]);
			

		}
		 void UNION(int x,int y)
		{
			x=find(x);
			y=find(y);
			if(size[x]<=size[y])
			{
				size[y]+=size[x];
				parent[x]=y;
			}
			else 
			{
				size[x]+=size[y];
				parent[y]=x;
			}
		}
	}
		  	 
		 		  
				   
				
				static class special{
					long x1,y1,x2,y2;
					//int id;
					special(long x1,long y1,long x2,long y2)
					{
						this.x1=x1;
						this.y1=y1;
						this.x2=x2;
						this.y2=y2;
						//this.id=id;
					}
					@Override
					    public int hashCode() {
				                int hash = 7;
	    hash = 31 * hash + (int) x1;
	    hash = 31 * hash + (int)x2;
	    hash = 31 * hash + (int)y1;
	    hash = 31 * hash + (int)y2;
	    return hash;
				            }
				              @Override
				            public boolean equals(Object o){
				                if (o == this) return true;
				                if (o.getClass() != getClass()) return false;
				                special t = (special)o;
				                return t.x1 == x1 && t.y1 == y1&&t.x2==x2&&t.y2==y2;
				            }
				}

				   
				     static long binexp(long a,long n)
				    {
				        if(n==0)
				            return 1;
				        long res=binexp(a,n/2);
				        if(n%2==1)
				            return res*res*a;
				        else 
				            return res*res;
				    }
				     
				    static long powMod(long base, long exp, long mod) {
				           if (base == 0 || base == 1) return base;
				           if (exp == 0) return 1;
				           if (exp == 1) return (base % mod+mod)%mod;
				           long R = (powMod(base, exp/2, mod) % mod+mod)%mod;
				           R *= R;
				           R %= mod;
				           if ((exp & 1) == 1) {
				               return (base * R % mod+mod)%mod;
				           }
				           else return (R %mod+mod)%mod;
				       }
				    static double dis(double x1,double y1,double x2,double y2)
				    {
				        return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
				    }
				    static long mod(long x,long y)
				        {
				            if(x<0)
				                x=x+(-x/y+1)*y;
				            return x%y;
				        }
				     public static  long pow(long b, long e) {
				                long r = 1;
				                while (e > 0) {
				                    if (e % 2 == 1) r = r * b ;
				                    b = b * b;
				                    e >>= 1;
				                }
				                return r;
				            }
				    private static void sort(long[] arr) {
				            List<Long> list = new ArrayList<>();
				            for (long object : arr) list.add(object);
				            Collections.sort(list);
				        //Collections.reverse(list);
				            for (int i = 0; i < list.size(); ++i) arr[i] = list.get(i);
				        }
				    private static void sort2(long[] arr) {
				            List<Long> list = new ArrayList<>();
				            for (Long object : arr) list.add(object);
				            Collections.sort(list);
				        Collections.reverse(list);
				            for (int i = 0; i < list.size(); ++i) arr[i] = list.get(i);
				        }
				     static class FastScanner
		{
		    private int BS = 1 << 16;
		    private char NC = (char) 0;
		    private byte[] buf = new byte[BS];
		    private int bId = 0, size = 0;
		    private char c = NC;
		    private double cnt = 1;
		    private BufferedInputStream in;
		 
		    public FastScanner() {
		        in = new BufferedInputStream(System.in, BS);
		    }
		 
		    public FastScanner(String s) {
		        try {
		            in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
		        } catch (Exception e) {
		            in = new BufferedInputStream(System.in, BS);
		        }
		    }
		 
		    private char getChar() {
		        while (bId == size) {
		            try {
		                size = in.read(buf);
		            } catch (Exception e) {
		                return NC;
		            }
		            if (size == -1) return NC;
		            bId = 0;
		        }
		        return (char) buf[bId++];
		    }
		 
		    public int nextInt() {
		        return (int) nextLong();
		    }
		 
		    public int[] nextInts(int N) {
		        int[] res = new int[N];
		        for (int i = 0; i < N; i++) {
		            res[i] = (int) nextLong();
		        }
		        return res;
		    }
		 
		    public long[] nextLongs(int N) {
		        long[] res = new long[N];
		        for (int i = 0; i < N; i++) {
		            res[i] = nextLong();
		        }
		        return res;
		    }
		 
		    public long nextLong() {
		        cnt = 1;
		        boolean neg = false;
		        if (c == NC) c = getChar();
		        for (; (c < '0' || c > '9'); c = getChar()) {
		            if (c == '-') neg = true;
		        }
		        long res = 0;
		        for (; c >= '0' && c <= '9'; c = getChar()) {
		            res = (res << 3) + (res << 1) + c - '0';
		            cnt *= 10;
		        }
		        return neg ? -res : res;
		    }
		 
		    public double nextDouble() {
		        double cur = nextLong();
		        return c != '.' ? cur : cur + nextLong() / cnt;
		    }
		 
		    public double[] nextDoubles(int N) {
		        double[] res = new double[N];
		        for (int i = 0; i < N; i++) {
		            res[i] = nextDouble();
		        }
		        return res;
		    }
		 
		    public String next() {
		        StringBuilder res = new StringBuilder();
		        while (c <= 32) c = getChar();
		        while (c > 32) {
		            res.append(c);
		            c = getChar();
		        }
		        return res.toString();
		    }
		 
		    public String nextLine() {
		        StringBuilder res = new StringBuilder();
		        while (c <= 32) c = getChar();
		        while (c != '\n') {
		            res.append(c);
		            c = getChar();
		        }
		        return res.toString();
		    }
		 
		    public boolean hasNext() {
		        if (c > 32) return true;
		        while (true) {
		            c = getChar();
		            if (c == NC) return false;
		            else if (c > 32) return true;
		        }
		    }
		}

				     static class Pair implements Comparable<Pair>{
				            public long x, y,z;
				            public Pair(long x1, long y1,long z1) {
				                x=x1;
				                y=y1;
				                z=z1;
				            }
				             public Pair(long x1, long y1) {
				                x=x1;
				                y=y1;
				    
				            }
				            
				            @Override
				            public int hashCode() {
				                return (int)(x + 31 * y);
				            }
				            public String toString() {
				                return x + " " + y+" "+z;
				            }
				            @Override
				            public boolean equals(Object o){
				                if (o == this) return true;
				                if (o.getClass() != getClass()) return false;
				                Pair t = (Pair)o;
				                return t.x == x && t.y == y&&t.z==z;
				            }
				    public int compareTo(Pair o)
				    {
				    	if(x==o.x)
				    		return -1;
				    
				    	return (int)(o.x-x);
				     
				        }
				     
				    }
				    
				    }

				     
