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.
//------------------>>>>>>>>>>>>>>>> HI . HOW ARE YOU? <<<<<<<<<<<<<<<<<<<<<<<<<<<<<------------------------------

import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.List;
import java.util.StringTokenizer;

//---------------------------->>>>>>>>>>>>>>>>>>>>>> FK OFF <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<-------------------

//--------------------------->>>>>>>>>>>>>>>>>>>>>>>> HACKER MF <<<<<<<<<<<<-------------------------------------

public class practice{
    static long[] count,count1,count2;
    static boolean[] prime;
    static boolean flag;
    static int[] spf;
    static Node[] nodes,nodes1,nodes2;
    static long[] arr;
    static long[][] cost;
    static int[] arrInt,darrInt,farrInt;
    static long[][] dp;
    static char[] ch,ch1,ch2;
    static long[] darr,farr;
    static char[][] mat,mat1;
    static boolean[] vis;
    static long x,h;
    static long maxl,sum,total;
    static double dec;
    static long mx = (long)1e7;
    static long inf = (long)1e18;
    static String s,s1,s2,s3,s4;
    static long minl;
    static long mod = (long)(1e9)+7;
    // static int minl = -1;
    // static long n;
    static int n,n1,n2,q,r1,c1,r2,c2;
    static int arr_size = (int)2e5+10;
    static long a;
    static long b;
    static long c;
    static long d;
    static long y,z;
    static int m,m1;
    static long ans;
    static long k;
    static FastScanner sc;
    static String[] str,str1;
    static Set<Long> set,set1,set2;
    static SortedSet<Long> ss;
    static List<StringBuilder> list,list1,list2,list3;
    static PriorityQueue<Node> pq,pq1;
    static LinkedList<Node> ll,ll1,ll2;
    static Map<Integer,List<Integer>> map;
    static Map<Integer,Integer> map2;
    static Map<Integer,Long> mapL,mapR;
    static Map<Integer,Node> map1;
    static StringBuilder sb,sb1,sb2;
    static int index;
    static int[] dx = {0,-1,0,1,-1,1,-1,1};
    static int[] dy = {-1,0,1,0,-1,-1,1,1};

    static class Node{
        long first;
        int second;
        Node(long f,int s){
            this.first = f;
            this.second = s;
        }
    }

    static LNode head = null;
    static LNode tail = null;

    static class LNode{
        long key;
        long val;
        LNode next;
        LNode prev;
        LNode(long key,long val){
            this.key = key;
            this.val = val;
            this.next = null;
            this.prev = null;
        }
        LNode(long val){
            this.key = -1;
            this.val = val;
            this.next = null;
            this.prev = null;
        }
    }


//     public static void solve(){
//
//        FastScanner sc = new FastScanner();
//        int t = sc.nextInt();
//        // int t = 1;
//        for(int tt = 1 ; tt <= t ; tt++){
//
//            System.out.println("Case #"+tt+": "+ ans);
//
//        }
//
//     }

    //--------------->>>>IF YOU ARE HERE FOR QUICKSORT HACK THEN SORRY NO HACK FOR YOU<<<------------------------------

    public static void solve() {

        int n = 10;
        int sa = 0;
        int sbb = 0;
        int pa = 0;
        int pb = 0;
        int remA = 5;
        int remB = 5;

        for(int i = 0 ; i < n ; i++){

            if(i%2 == 0){
                if(ch[i] == '1')
                    sa += 1;
                else if(ch[i] == '?')
                    pa += 1;
                remA -= 1;
            }
            else{
                if(ch[i] == '1')
                    sbb += 1;
                else if(ch[i] == '?')
                    pb += 1;
                remB -= 1;
            }

            int maxlA = sa + pa;
            int minlB = sbb;

//            for(int j = i+1 ; j < n ; j++){
//                if(j%2 == 1 && ch[j] == '1')
//                    minlB += 1;
//                if(j%2 == 0 && ch[j] == '1')
//                    maxlA += 1;
//            }

            if(maxlA > minlB+remB){
                sb.append(i+1).append("\n");
                return;
            }

            int maxlB = sbb + pb;
            int minlA = sa;

//            for(int j = i+1 ; j < n ; j++){
//                if(j%2 == 0 && ch[j] == '1')
//                    minlA += 1;
//                if(j%2 == 1 && ch[j] == '1')
//                    maxlB += 1;
//            }

            if(maxlB > minlA+remA){
                sb.append(i+1).append("\n");
                return;
            }

        }
        sb.append(n).append("\n");

    }

    //----------->>>>>>> SPEED UP SPEED UP . THIS IS SPEEDFORCES . SPEED UP SPEEEEEEEEEEEEEEEEEEEEEEEEEEDDDDDD <<<<<<<------------------

    public static void main(String[] args) {

        sc = new FastScanner();
        // Scanner sc = new Scanner(System.in);
        sb = new StringBuilder();
        int t = sc.nextInt();
//        int t = 1;
        while(t > 0){

//             k = sc.nextLong();
            // x = sc.nextLong();
            // y = sc.nextLong();
            // z = sc.nextLong();

//            a = sc.nextLong();
//             b = sc.nextLong();
//             c = sc.nextLong();
//             d = sc.nextLong();
//
//             x = sc.nextLong();
//             y = sc.nextLong();
//             z = sc.nextLong();
            // d = sc.nextLong();

//            n = sc.nextInt();

            // n1 = sc.nextInt();

//            m = sc.nextInt();
//             q = sc.nextInt();

//             a = sc.nextLong();
//             b = sc.nextLong();

//             k = sc.nextLong();

//            x = sc.nextLong();
            // d = sc.nextLong();

//            s = sc.next();

            ch = sc.next().toCharArray();
//             ch1 = sc.next().toCharArray();

//             m = sc.nextInt();
            // n = 6;

//            arr = new long[n];
//            for(int i = 0 ; i < n ; i++){
//                arr[i] = sc.nextLong();
//            }

//            arrInt = new int[n];
//            for(int i = 0 ; i < n ; i++){
//                arrInt[i] = sc.nextInt();
//            }

            // x = sc.nextLong();
            // y = sc.nextLong();
//             ch = sc.next().toCharArray();
//            m = n;
////             m = sc.nextInt();
//            darr = new long[m];
//            for(int i = 0 ; i < m ; i++){
//                darr[i] = sc.nextLong();
//            }
            // k = sc.nextLong();
            // m = n;
//             darrInt = new int[n];
//             for(int i = 0 ; i < n ; i++){
//                 darrInt[i] = sc.nextInt();
//             }

//             farr = new long[n];
//             for(int i = 0 ; i < n ; i++){
//                 farr[i] = sc.nextLong();
//             }

            // farrInt = new int[m];
            // for(int i = 0; i < m ; i++){
            //     farrInt[i] = sc.nextInt();
            // }

            // m = n;
//            mat = new int[2][n];
//            for(int i = 0 ; i < 2 ; i++){
//                for(int j = 0 ; j < n ; j++){
//                    mat[i][j] = sc.nextInt();
//                }
//            }

//             m = n;
//             mat = new char[n][m];
//             for(int i = 0 ; i < n ; i++){
//                 String s = sc.next();
//                 for(int j = 0 ; j < m ; j++){
//                     mat[i][j] = s.charAt(j);
//                 }
//             }
//
//             str = new String[n];
//             for(int i = 0 ; i < n ; i++)
//                 str[i] = sc.next();

//             nodes = new Node[n];
//             for(int i = 0 ; i < n ;i++)
//                 nodes[i] = new Node(sc.nextLong(),(i));

            solve();
            t -= 1;
        }
        System.out.print(sb);

    }

    public static int log(double n,double base){

        if(n == 0 || n == 1)
            return 0;

        if(n == base)
            return 1;

        double num = Math.log(n);
        double den = Math.log(base);

        if(den == 0)
            return 0;

        return (int)(num/den);
    }

    public static boolean isPrime(long n) {
        // Corner cases
        if (n <= 1)
            return false;

        if (n <= 3)
            return true;

        // This is checked so that we can skip
        // middle five numbers in below loop
        if (n%2 == 0 || n%3 == 0)
            return false;

        for (int i=5; i*i<=n; i=i+6)
            if (n%i == 0 || n%(i+2) == 0)
                return false;

        return true;
    }

    public static void SpecialSieve(int MAXN)
    {
        spf = new int[MAXN];
        spf[1] = 1;
        for (int i=2; i<MAXN; i++)

            // marking smallest prime factor for every
            // number to be itself.
            spf[i] = i;

        // separately marking spf for every even
        // number as 2
        for (int i=4; i<MAXN; i+=2)
            spf[i] = 2;

        for (int i=3; i*i<MAXN; i++)
        {
            // checking if i is prime
            if (spf[i] == i)
            {
                // marking SPF for all numbers divisible by i
                for (int j=i*i; j<MAXN; j+=i)

                    // marking spf[j] if it is not
                    // previously marked
                    if (spf[j]==j)
                        spf[j] = i;
            }
        }
    }

    public static ArrayList<Integer> getFactorization(int x)
    {
        ArrayList<Integer> ret = new ArrayList<Integer>();
        while (x != 1)
        {
            ret.add(spf[x]);
            x = x / spf[x];
        }
        return ret;
    }

    public static long gcd(long a, long b)
    {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    public static long lcm(long a, long b)
    {
        return (b/gcd(b, a % b)) * a;
    }

    public static long mod_inverse(long a,long mod){
        long x1=1,x2=0;
        long p=mod,q,t;
        while(a%p!=0){
            q = a/p;
            t = x1-q*x2;
            x1=x2; x2=t;
            t=a%p;
            a=p; p=t;
        }
        return x2<0 ? x2+mod : x2;
    }

    public static void swap(double[] curr,int i,int j){
        double temp = curr[j];
        curr[j] = curr[i];
        curr[i] = temp;
    }

    static final Random random=new Random();

    static void ruffleSortLong(long[] a) {
        int n=a.length;//shuffle, then sort
        for (int i=0; i<n; i++) {
            int oi=random.nextInt(n);
            long temp=a[oi];
            a[oi]=a[i]; a[i]=temp;
        }
        Arrays.sort(a);
    }

    static void ruffleSortInt(int[] a) {
        int n=a.length;//shuffle, then sort
        for (int i=0; i<n; i++) {
            int oi=random.nextInt(n);
            int temp=a[oi];
            a[oi]=a[i]; a[i]=temp;
        }
        Arrays.sort(a);
    }

    static void ruffleSortChar(char[] a) {
        int n=a.length;//shuffle, then sort
        for (int i=0; i<n; i++) {
            int oi=random.nextInt(n);
            char temp=a[oi];
            a[oi]=a[i]; a[i]=temp;
        }
        Arrays.sort(a);
    }

    static long binomialCoeff(long n, long k){

        long res = 1;

        // Since C(n, k) = C(n, n-k)
        if (k > n - k)
            k = n - k;

        // Calculate value of
        // [n * (n-1) *---* (n-k+1)] / [k * (k-1) *----* 1]
        for (long i = 0; i < k; ++i) {
            res = (res*(n - i));
            res = (res/(i + 1));
        }

        return res;
    }

    static long mod(long x)
    {
        long y = mod;
        long result = x % y;
        while (result < 0)
        {
            result += y;
        }
        return result;
    }

    static long[] fact;

    public static long inv(long n){
        return power(n, mod-2);
    }

    public static void fact(int n){
        fact = new long[n+1];
        fact[0] = 1;
        for(int j = 1;j<=n;j++)
            fact[j] = (fact[j-1]*(long)j)%mod;
    }

    public static long binom(int n, int k){

        long prod = fact[n];
        prod*=inv(fact[n-k]);
        prod%=mod;
        prod*=inv(fact[k]);
        prod%=mod;
        return prod;
    }

    static long power(long x, long y){
        if (y == 0)
            return 1;
        if (y%2 == 1)
            return (x*power(x, y-1))%mod;
        return power((x*x)%mod, y/2)%mod;
    }

    static void sieve(int n){

        prime = new boolean[n+1];
        for(int i=2;i<n;i++)
            prime[i] = true;

        for(int p = 2; p*p <=n; p++)
        {
            if(prime[p])
            {
                for(int i = p*p; i <= n; i += p)
                    prime[i] = false;
            }
        }

    }

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

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

    static int max(int a,int b){
        if(a>b)
            return a;
        else
            return b;
    }
    static double max(double a,double b){
        if(a>b)
            return a;
        else
            return b;
    }
    static double min(double a,double b){
        if(a>b)
            return b;
        else
            return a;
    }

    static int min(int a,int b){
        if(a>b)
            return b;
        else
            return a;
    }

    static long max(long a,long b){
        if(a>b)
            return a;
        else
            return b;
    }

    static long min(long a,long b){
        if(a>b)
            return b;
        else
            return a;
    }

    static long sq(long num){
        return num*num;
    }

    static double sq(double num){
        return num*num;
    }

    static long sqrt(long num){
        return (long)Math.sqrt(num);
    }

    static double sqrt(double num){
        return Math.sqrt(num);
    }

    static private void removeNode(LNode n){
        if(n.prev!=null){
            n.prev.next = n.next;
        }else{
            head = n.next;
        }

        if(n.next!=null){
            n.next.prev = n.prev;
        }else{
            tail = n.prev;
        }
    }

    static private void offerNode(LNode n){

        if(tail!=null){
            tail.next = n;
        }

        n.prev = tail;
        n.next = null;
        tail = n;

        if(head == null){
            head = tail;
        }
    }

    static class FastScanner {

        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");
        String next() {
            while (!st.hasMoreTokens())
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
        //        void readArray(int n) {
//            arr = new long[n];
//            for (int i = 0; i < n; i++)
//                arr[i] = nextLong();
//        }
        long nextLong() {
            return Long.parseLong(next());
        }
    }

}