Connectivity Potential

Problem

Space elevator and shuttle (SES) systems have been set up high above the earth, and each system has a number of stations. Stations that need high-frequency transit are connected directly, while the others are connected through another station in the system. If a space traveller has to travel from one station to another that is not directly connected, the traveller is directed along a route with the minimum number of hops needed to reach the destination.

The figure below shows an SES system with four stations, where the directed arcs are the direct connections between pairs of stations. Station 1 is directly connected to Station 2 and Station 4, and it is indirectly connected to Station 3 through Station 2. In this example, the longest route between any two stations is 3 hops, and the system has two such routes: from station 2 to station 4, and from station 4 to station 1.

The connectivity potential of an SES system is the number of hops in the longest route multiplied by the number of routes with that many hops. So the connectivity potential of the SES system in the figure is $3 \times 2 = 6$ .

Here, a route is counted once for every ordered pair $(i, j)$ of distinct stations such that $j$ is reachable from $i$ , and its length is the minimum number of hops from $i$ to $j$ . Unreachable pairs are not counted. If there is no route at all, the connectivity potential is 0.

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 1000$ ).

Each test case describes one SES system. Its first line contains the number of stations $S$ ( $1 \le S \le 40$ ). Each of the next $S$ lines is a string of $S$ characters, each 0 or 1, describing the connections. If the $j$ -th character of the $i$ -th line is 1, there is a direct connection from station $i$ to station $j$ ; if it is 0, there is no direct connection.

Output

For each test case, print one line with the prefix Case #x: followed by the connectivity potential of that SES system. Here $x$ is the case number, starting from 1 and increasing by one for each test case.