# Graph

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65768/65768 K (Java/Others)

## Description

Everyone knows how to calculate the shortest path in a directed graph. In fact, the opposite problem is also easy. Given the length of shortest path between each pair of vertexes, can you find the original graph?

## Input

The first line is the test case number T (T ≤ 100).
First line of each case is an integer N (1 ≤ N ≤ 100), the number of vertexes.
Following N lines each contains N integers. All these integers are less than 1000000.
The jth integer of ith line is the shortest path from vertex i to j.
The ith element of ith line is always 0. Other elements are all positive.

## Output

For each case, you should output “Case k: ” first, where k indicates the case number and counts from one. Then one integer, the minimum possible edge number in original graph. Output “impossible” if such graph doesn't exist.

## Sample Input

3
3
0 1 1
1 0 1
1 1 0
3
0 1 3
4 0 2
7 3 0
3
0 1 4
1 0 2
4 2 0

## Sample Output

Case 1: 6
Case 2: 4
Case 3: impossible

lcy

## Source

The 36th ACM/ICPC Asia Regional Chengdu Sit