1 #include<stdio.h> 2 3 int a[32][32]; 4 int m; 5 6 int fun() 7 { 8 int i,j,k; 9 for(i=0;i<m;i++) 10 if(a[i][i]!=0) return 1; 11 12 for(i=0;i<m;i++) 13 for(j=0;j<m;j++) 14 if(i!=j) 15 if(a[i][j]<=0) return 2; 16 17 for(i=0;i<m;i++) 18 for(j=0;j<m;j++) 19 if(a[i][j]!=a[j][i]) return 3; 20 21 for(i=0;i<m;i++) 22 for(j=0;j<m;j++) 23 for(k=0;k<m;k++) 24 if(i!=j&&j!=k&&i!=k) 25 if(a[i][j]+a[j][k]<a[i][k]) 26 /* if(a[i][j]+a[j][k]>=a[i][k]) 27 if(i==j||j==k||i==k) */return 4; 28 29 return 0; 30 } 31 32 int main() 33 { 34 int i,j,t; 35 scanf("%d",&t); 36 while(t--) 37 { 38 scanf("%d",&m); 39 for(i=0;i<m;i++) 40 for(j=0;j<m;j++) 41 scanf("%d",&a[i][j]); 42 if(fun()) printf("%d\n",fun()); 43 else 44 printf("0\n"); 45 } 46 return 0; 47 }