import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N = 6;
    static int n;
    static char[][] g = new char[N][N];
    static char[][] bg = new char[N][N];
    static int[] dx = new int[] {0,-1,0,1,0};
    static int[] dy = new int[] {-1,0,1,0,0};
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        while(n-- >0)
        {
            int res = 10;
            for(int i=0;i<5;i++)
            {
                bg[i] = sc.next().toCharArray();
            }
                //每行5位 每位有0/1两种状态 对应10进制的0~31
                //枚举对第一行的所有可能操作 每一位的0表示不摁 1表示摁 ，如11111 表示全摁，00000表示全不摁
                //每对第一行进行操作要事先备份
                for(int op=0;op<32;op++)
                {
                    for(int k=0;k<5;k++)
                    {
                        for(int q=0;q<5;q++)
                            g[k][q] = bg[k][q];
                    }

                    int stp = 0;
                    for(int i=0;i<5;i++)
                    {
                        int u = op>>i &1;
                        if(u==1)
                        {
                            stp++;
                            turn(0,i);
                        }
                    }

                    for(int i=0;i<4;i++)
                    {
                        for(int j=0;j<5;j++)
                        {
                            if(g[i][j]=='0')
                            {
                                stp++;
                                turn(i+1,j);
                            }
                        }
                    }

                    boolean dark = false;
                    for(int j=0;j<5;j++)
                    {
                        if(g[4][j]=='0')
                        {
                            dark = true;
                            break;
                        }
                    }
                    if(dark==false) res = Math.min(res,stp);

                }
            if(res>6) res = -1;
            System.out.println(res);

        }
    }

    static void turn(int x,int y)
    {
        for(int i=0;i<5;i++)
        {
            int a = x+dx[i],b = y+dy[i];
            if(a<0 || a>=5 || b<0 || b>=5) continue;
            g[a][b] ^= 1;
        }
    }

}

import java.util.Scanner;

public class Main {
    static int N = 50;
    static int[] a = new int[N];
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        a[0] = 0;
        a[1] = 1;
        for(int i=2;i<n;i++)
        {
            a[i] = a[i-1] + a[i-2];
        }
        for(int i=0;i<n;i++)
            System.out.print(a[i]+" ");
    }

}

import java.util.Scanner;

public class Main {
    static int N = 20;
    static boolean[] used = new boolean[11];
    static int n,res;
    static int[] nums = new int[N];
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        dfs(0);
        System.out.println(res);
    }

    static int calc(int l,int r)
    {
        int res = 0;
        for(int i=l;i<=r;i++)
        {
                res = res * 10 + nums[i];
        }
        return res;
    }


    static void dfs(int u)
    {
        if(u==9)
        {
            for(int i=0;i<7;i++)
            {
                for(int j=i+1;j<8;j++)
                {
                    int a = calc(0,i);
                    int b = calc(i+1,j);
                    int c = calc(j+1,8);
                    if(a*c+b == c*n) res++;
                }
            }
        }

        for(int i=1;i<=9;i++)
        {
            if(used[i]==false)
            {
                nums[u] = i;
                used[i] = true;
                dfs(u+1);
                used[i] = false;
            }
        }

    }
}

import java.util.Scanner;

public class Main {
    static int N = 100;
    static int[] st = new int[N];//st[0]代表没用过，st[i]代表这个位置用哪个数
    static int n,m;
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        dfs(1,1);
    }

    static void dfs(int u,int start)
    {
        if(u>m)
        {
            for(int i=1;i<=m;i++)
            {
                System.out.print(st[i]+" ");
            }
            System.out.println();
            return;
        }

        for(int i=start;i<=n;i++)
        {
              st[u] = i;
              dfs(u+1,i+1);
              st[u] = 0;
        }
    }
}

package Acwing算法练习.蓝桥第一章递归与递推;

import java.util.Scanner;

public class 递归实现排列型枚举 {
    static int N = 15;
    static int[] st = new int[N];//状态:0代表没用过，1~n代表这个位置用那个数
    static boolean[] used = new boolean[N];
    static int n;
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        dfs(1);
    }

    static void dfs(int u)
    {
        if(u>n)//遍历结束条件
        {
            for(int i=1;i<=n;i++)
            {
                System.out.print(st[i]+" ");
            }
            System.out.println();
        }

        for(int i=1;i<=n;i++)//依次枚举每个分支，当前位置可以填那些数
        {
            if(used[i]==false)
            {
                st[u] = i;
                used[i] = true;
                dfs(u+1);
                st[u] = 0;
                used[i] = false;
            }
        }

    }

}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
    static int N = 20;
    static int[] st = new int[N];//状态表示，0表示还没考虑，1表示选，2表示没选
    static int n;
    public static void main(String[] args) throws IOException
    {
        Scanner sc = new Scanner(System.in);
        BufferedReader br =  new BufferedReader(new InputStreamReader(System.in));
        String s[] = br.readLine().split("\\s+");
        n = Integer.parseInt(s[0]);
        dfs(0);

    }

    static void dfs(int u)
    {
        if(u==n)//终止条件
        {
            for(int i=0;i<n;i++)
            {
                if(st[i]==1)
                    System.out.print(i+1+" ");
            }
            System.out.println();
            return;
        }

        st[u] = 2;//不选
        dfs(u+1);
        st[u] = 0;

        st[u] = 1;
        dfs(u+1);
        st[u] = 0;


    }


}

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    static int N = 110,M = 100010;
    static int[] s = new int[N];// s 表示集合里的数字
    static int[] f = new int[M];// f表示sg的值
    static int n,m;
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int res = 0;
        Arrays.fill(f,-1);
        for(int i=0;i<n;i++)
        {
            s[i] = sc.nextInt();
        }
        m = sc.nextInt();
        for(int i=0;i<m;i++)
        {
            int x = sc.nextInt();
            res ^= sg(x);
        }

        if(res!=0) System.out.println("Yes");
        else System.out.println("No");
    }

    static int sg(int x)//求每堆石子的sg值
    {
        if(f[x]!=-1) return f[x];//记忆和搜索，如果搜索过了直接return
        Set<Integer> S = new HashSet<>();
        for(int i=0;i<n;i++)
        {
            int sum = s[i];//每次取sum个石子， 剩余的石子个数为x - sum
            if(x>=sum ) S.add(sg(x-sum));
        }
        for(int i=0;;i++)//mex集合中没出现过的最小的非负整数
        {
            if(!S.contains(i))
                return f[x] = i;
        }
    }


}

import java.util.Scanner;
//根据第奇数阶台阶判断，对所有的奇数阶台阶进行^,如果得0，那么先手必败
//如果奇数阶台阶不得0.那么我们可以通过先手转化成0，让对手面对奇数阶台阶输
//如果只有偶数阶台阶有的话，那么不管怎么先手都可以通过最佳方案赢
public class Main {
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n+1];
        int res = 0;
        for(int i=1;i<=n;i++)
        {
            a[i] = sc.nextInt();
            if(i%2==1)
                res^=a[i];
        }
        if(res!=0) System.out.println("Yes");
        else System.out.println("No");
    }
}

import java.util.Scanner;

public class Main {
    //先手必胜:如果这对数里面全部亦或（^）起来等于x(不等于0)，那么先手一定赢
    //先手必输:如果这对数里面全部亦或（^）起来等于0，那么先手一定输
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        int res = 0;
        for(int i=0;i<n;i++)
        {
            a[i] = sc.nextInt();
            res ^= a[i];
        }
        if(res!=0) System.out.println("Yes");
        else System.out.println("No");

    }
}

package Acwing算法练习.第五章dp;

import java.util.Arrays;
import java.util.Scanner;
//f[u][0]表示以u为根节点，并且不包括u的最大快乐指数
//f[u][1]表示以u为根节点，并且包括u的最大快乐指数
public class 没有上司的舞会 {
    static int N = 100010;
    static int[] happy = new int[N];
    static boolean[] has_fa = new boolean[N];
    static int[][] f = new int[N][2];
    static int[] e = new int[N],ne = new int[N],h = new int[N];
    static int idx;
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i=1;i<=n;i++) happy[i] = sc.nextInt();
        Arrays.fill(h,-1);
        for(int i=0;i<n-1;i++)//n-1条边
        {
            int b = sc.nextInt();
            int a = sc.nextInt();
            has_fa[b] = true;//如果有父节点，就true
            add(a,b);
        }

        int root = 1;
        while(has_fa[root]) root++;
        dfs(root);
        System.out.println(Math.max(f[root][0],f[root][1]));

    }

    static void dfs(int u)
    {
        f[u][1] = happy[u];
        for(int i=h[u];i!=-1;i=ne[i])
        {
            int j = e[i];
            dfs(j);//子结点
            f[u][1] += f[j][0];
            f[u][0] += Math.max(f[j][1],f[j][0]);
        }
    }

    static void add(int a,int b)
    {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }

}