//这里填你的代码^^
// Problem: 费解的开关
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/97/
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-falign-functions,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3,2)
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using i64=long long;
#define int long long
#define ull unsigned long long
#define PII pair<int,int>
#define eps 1e-7
#define puts(res) cout<<res<<'\n'
#define put cout<<'\n'
#define cout(a) cout<<a<<'\n';
#define debug(a) cout<<#a<<"="<<a<<endl
#define debug2(a,b) cout<<#a<<"="<<a<<" "<<#b<<"="<<b<<endl
#define debug3(a,b,c) cout<<#a<<"="<<a<<" "<<#b<<"="<<b<<" "<<#c<<"="<<c<<endl
#define mem1(a) memset(a,-1,sizeof(a))
#define mem0(a) memset(a,0,sizeof(a))
#define mem(a) memset(a,0x3f,sizeof(a))
#define fup(o,a,b) for(int o=a;o<=b;o++)
#define up(a,b) for(int o=a;o<=b;o++)
#define dn(a,b) for(int o=a;o>=b;o--)
#define fdn(o,a,b) for(int o=a;o>=b;o--)
#define show(a) for(auto it:a)cout<<it<<" ";
#define cvec(a) for(auto &it:a)cin>>it;
#define sz(v) (int)v.size()
#define all(a) (a).begin(),(a).end()
#define range(a,n) a+1,a+1+n
#define crange(a,n) up(1,n)cin>>a[o]
#define showcase(a,n) up(1,n)cout<<a[o]<<" \n"[o==n];
#define rall(x) (x).rbegin(), (x).rend()
#define YES {puts("YES");return;}
#define NO {puts("NO");return;}
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define endl '\n'
#define fi first
#define se second
#define pb emplace_back
#define pob pop_back
#define pof pop_front
#define pf emplace_front
#define db double
#define MAX 0x7ffffffffffffffff
#define INF 0x3f3f3f3f3f3f3f3f
const int N=2e5+10;
int n,m;
int a[6][6];
int tmp[6][6];
bool yes(int x,int y){
if(x<1||x>5)return false;
if(y<1||y>5)return false;
return true;
}
void turn(int x,int y){
if(yes(x,y))a[x][y]^=1;
if(yes(x+1,y))a[x+1][y]^=1;
if(yes(x-1,y))a[x-1][y]^=1;
if(yes(x,y+1))a[x][y+1]^=1;
if(yes(x,y-1))a[x][y-1]^=1;
}
void solve(){
//try it again.
fup(i,1,5){
fup(j,1,5){
char x;cin>>x;
a[i][j]=x-'0';
}
}
int ans=INF;
for(int i=0;i<(1<<5);i++){
int res=0;
memcpy(tmp,a,sizeof tmp);
fup(j,0,4){
if(i>>j&1){
res++;
turn(1,j+1);
}
}
fup(i,1,4){
fup(j,1,5){
if(!a[i][j]){
res++;
turn(i+1,j);
}
}
}
bool falg=false;
fup(i,1,5)if(!a[5][i])falg=true;
if(!falg)ans=min(ans,res);
memcpy(a,tmp,sizeof a);
}
if(ans>6)cout<<-1<<endl;
else cout<<ans<<endl;
}
signed main(){
IOS;
int __;
cin>>__;
while(__--)
solve();
return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
可以用一个bool数组记录每个单词的最后一个字符插入时的idx,这样应该比set快
受教了