1 #include<cstdio>
 2 #include<cstring>
 3 #define maxn 110
 4 int ds[maxn][maxn];
 5 bool vis[maxn][maxn];
 6 int mat[maxn][maxn];
 7 void floyd(int n)
 8 {
 9     for(int k=0;k<n;k++)
10     {
11         for(int i=0;i<n;i++)
12         {
13             if(i==k) continue;
14             for(int j=0;j<n;j++)
15             {
16                 if(k==j)continue;
17                 if(ds[i][j]>=ds[i][k]+ds[k][j])
18                 {
19                     vis[i][j]=1;
20                     ds[i][j]=ds[i][k]+ds[k][j];
21                 }
22             }
23         }
24     }
25 }
26 int main()
27 {
28  int cas,n;
29    scanf("%d",&cas);
30    for(int tt=1;tt<=cas;tt++)
31    {
32          scanf("%d",&n);
33          for(int i=0;i<n;i++)
34           for(int j=0;j<n;j++)
35         {
36           scanf("%d",mat[i]+j);
37           ds[i][j]=mat[i][j];
38         }
39         memset(vis,0,sizeof(vis));
40         floyd(n);
41         int res=0;
42         bool tag=0;
43       for(int i=0;i<n;i++)
44       {
45           for(int j=0;j<n;j++)
46         {
47           if(vis[i][j]&&ds[i][j]==mat[i][j])
48               res++;
49           else if(ds[i][j]<mat[i][j])
50           {
51                 tag=1;
52               break;
53           }
54         }
55          if(tag)break;
56       }
57         printf("Case %d: ",tt);
58         if(tag)
59             printf("impossible\n");
60         else printf("%d\n",n*(n-1)-res);
61 
62    }
63  return 0;
64 }