연결 잠재력

지구 상공에 우주 엘리베이터와 셔틀(SES) 시스템이 설치되어 있고, 각 시스템에는 여러 개의 정거장이 있다. 운행이 잦아야 하는 정거장끼리는 직접 연결되어 있고, 나머지는 시스템 안의 다른 정거장을 거쳐 연결된다. 우주 여행자가 직접 연결되지 않은 정거장으로 이동해야 하면, 목적지까지 거치는 홉 수가 가장 적은 경로로 안내받는다.

아래 그림은 정거장 4개로 이루어진 SES 시스템이다. 방향이 있는 화살표는 두 정거장 사이의 직접 연결을 나타낸다. 정거장 1은 정거장 2와 정거장 4에 직접 연결되어 있고, 정거장 2를 거쳐 정거장 3에 간접적으로 연결되어 있다. 이 예에서 두 정거장 사이의 가장 긴 경로는 3홉이며, 그런 경로는 정거장 2에서 4로 가는 경로와 정거장 4에서 1로 가는 경로로 두 개다.

SES 시스템의 연결 잠재력은 가장 긴 경로의 홉 수와 그 홉 수를 가진 경로의 개수를 곱한 값이다. 따라서 위 그림의 SES 시스템의 연결 잠재력은 $3 \times 2 = 6$이다.

여기서 경로는 서로 다른 두 정거장의 순서쌍 $(i, j)$ 중 $i$에서 $j$로 갈 수 있는 것마다 하나씩 세며, 그 길이는 $i$에서 $j$까지의 최소 홉 수다. 도달할 수 없는 순서쌍은 세지 않는다. 그런 경로가 하나도 없으면 연결 잠재력은 0이다.

첫째 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 1000$)가 주어진다.

각 테스트 케이스는 SES 시스템 하나를 나타낸다. 첫 줄에 정거장의 수 $S$ ($1 \le S \le 40$)가 주어진다. 다음 $S$개의 줄에는 정거장 사이의 연결이 0과 1로 이루어진 길이 $S$의 문자열로 주어진다. $i$번째 줄의 $j$번째 문자가 1이면 정거장 $i$에서 정거장 $j$로 가는 직접 연결이 있고, 0이면 직접 연결이 없다.

각 테스트 케이스마다 한 줄에 Case #x: 뒤에 그 SES 시스템의 연결 잠재력을 출력한다. $x$는 1부터 시작해 테스트 케이스마다 1씩 증가하는 번호다.