给定一个数由di 个数字i(1≤i≤9) 和若干个0（可以没有0）组成，数字可以按照任意顺序排列，最终组成一个非负整数。

现在小强想问如果他想让这个数被11整除，那这个数最少要多少位。

输入格式 本题多测。

第一行，⼀个整数 T ，表示有 T 组数据。

接下来 T 行，每⾏ 9 个非负整数，第 i 个代表 di 。

输出格式 对于每组数据输出一行⼀个整数，表示最小的位数。

如果⽆论如何都不能使之能被 11 整除，输出 −1。

样例 input

3

0 0 2 0 1 0 0 0 0

3 0 2 1 0 1 0 0 0

5 1 0 0 0 0 1 0 0

output

5

9

11

explanation

每组可能的一组解： 30503，113340601，17101010102

d<=100 可以使用dfs 但是希望使用dp

#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#define int long long
#define endl "\n"
using namespace std;
bool Men;
const int N=200005;
const int mod=998244353;


inline void write(int x){if(x<0) putchar('-'),x=-x;if(x>9) write(x/10);putchar(x%10+'0');return;}
inline int read() {int x=0,f=1; char ch=getchar();while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar();}while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;}
void add(int &x,int y){x=(x+y)%mod;}
int ksc(int m,int n,int p){int ans=0;while(n){if(n%2==1){n=n-1;ans=(ans+m)%p;}n=n/2;m=(m+m)%p;}return ans;}
int ksm(int base,int power,int p){int result=1;while(power>0){if(power&1){result=result*base%p;}power>>=1;base=(base*base)%p;}return result;}
int mod_inverse(int a){return ksm(a,mod-2,mod);}
int inv(int numerator,int denominator){int inverse_denominator = mod_inverse(denominator);int result=(1LL*numerator*inverse_denominator)%mod;return result;}

int d[11];
int dp[15][15][2];// 奇数和  偶数和   该放置 奇数 偶数 0/1  ====    总使用次数 
int tot=0;
bool Mbe;
signed main(){
	debug("%.8lfMB\n",(&Men-&Mbe)/1048576.0);
	int T=read();
	while(T--){
		for(int i=1;i<=9;i++) {
			d[i]=read();
		}
		memset(dp,0x3f3f3f3f,sizeof(dp));
		//dp[][][i]=dp[j-a[k]][][i-1] 
		dp[0][0][0]=1;
		dp[0][0][1]=1;
		for(int i=0;i<=10;i++){
			for(int j=0;j<=10;j++){
				for(int k=1;k<=9;k++){
					for(int q=1;q<=d[k];q++){
						dp[i][j][0]=min(dp[i][j][1]+1,dp[i][j][0]);
						dp[i][j][1]=min(dp[i][j][0]+1,dp[i][j][1]);
						
						dp[i][j][1]=min(dp[i][j][1],dp[i][(11+j-k)%11][0]+1);
						dp[i][j][0]=min(dp[i][j][0],dp[(11+i-k)%11][j][1]+1);
					}
				}
			}
		}
		int ans=0x3f3f3f3f;
		for(int i=1;i<=10;i++){
			for(int j=1;j<=10;j++){
				if(abs(i-j)%11==0){
					ans=min(ans,min(dp[i][j][0],dp[i][j][1]));
				}
			}
		}
		if(ans==0x3f3f3f3f) cout<<-1<<endl;
		cout<<ans<<endl;
	}
	
	
	
	
	debug("%.8lfms\n",1e3*clock()/CLOCKS_PER_SEC);
	return 0;
}