1 #include <iostream>
 2 #include <sstream>
 3 #include <ios>
 4 #include <iomanip>
 5 #include <functional>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <string>
 9 #include <list>
10 #include <queue>
11 #include <deque>
12 #include <stack>
13 #include <set>
14 #include <map>
15 #include <cstdio>
16 #include <cstdlib>
17 #include <cmath>
18 #include <cstring>
19 #include <climits>
20 #include <cctype>
21 using namespace std;
22 #define XINF INT_MAX
23 #define INF 0x3FFFFFFF
24 #define MP(X,Y) make_pair(X,Y)
25 #define PB(X) push_back(X)
26 #define REP(X,N) for(int X=0;X<N;X++)
27 #define REP2(X,L,R) for(int X=L;X<=R;X++)
28 #define DEP(X,R,L) for(int X=R;X>=L;X--)
29 #define CLR(A,X) memset(A,X,sizeof(A))
30 #define IT iterator
31 typedef long long ll;
32 typedef pair<int,int> PII;
33 typedef vector<PII> VII;
34 typedef vector<int> VI;
35 
36 int N;
37 int dist[105][105];
38 int vis[105][105];
39 int main()
40 {
41     ios::sync_with_stdio(false);
42 
43     int tst;
44     cin>>tst;
45     int cse = 0;
46     while(tst--)
47     {
48         CLR(dist,0);CLR(vis,0);
49 
50         cin>>N;
51         REP(i,N)
52         REP(j,N)
53         {
54             cin>>dist[i][j];
55         }
56         cout<<"Case "<<++cse<<": ";
57 
58         int ans = N*(N-1);
59         REP(k,N)
60         {
61             REP(i,N)
62             {
63                 REP(j,N)
64                 {
65                     if( i == k || j == k)continue;
66                     if(!vis[i][j] && dist[i][j] == dist[i][k]+dist[k][j])
67                     {
68                         ans--;
69                         vis[i][j] =1;
70                     }
71                     if( dist[i][j] > dist[i][k]+dist[k][j])
72                     {
73                         ans = -1;
74                         break;
75                     }
76                 }
77                 if( ans ==-1)
78                 {
79                     break;
80                 }
81             }
82             if(ans==-1)break;
83         }
84         if( ans == -1)
85         {
86             cout<<"impossible"<<endl;
87         }
88         else
89         {
90             cout<<ans<<endl;
91         }
92 
93     }
94 
95     return 0;
96 }