요정과 마녀

파리는 강력한 요정으로, 마법 막대기를 써서 사악한 마녀들로부터 요정의 나라를 지키려 한다. 마녀들은 날이 갈수록 강해지므로, 파리는 막대기를 배열해 넓이가 0이 아닌 볼록 다각형을 만들어 보호 주문을 걸어야 한다. 하지만 파리가 원하는 막대기를 아무거나 쓸 수는 없다. 요정의 나라에 있는 막대기들은 그래프를 이룬다. 막대기는 간선이고, 노드는 막대기 하나 이상이 만나는 끝점이다. 막대기는 끝점에서만 서로 닿으며, 마법 막대기라서 그 밖의 곳에서는 닿지 않는다. 파리가 막대기 하나를 뽑아 주문에 쓰면, 그 막대기와 노드를 공유하던 모든 막대기가 영원히 사라져 이후에 쓸 수 없다. 파리는 그래프에서 막대기 부분집합을 뽑아 넓이가 0이 아닌 볼록 다각형을 만들 수 있는 경우가 몇 가지인지 궁금해한다. 막대기는 모두 구별되며, 길이가 같아도 마찬가지다. 두 부분집합은 한쪽에만 들어 있는 막대기가 하나라도 있을 때 서로 다르다. 부분집합이 유효하려면, 그 안의 막대기를 모두 사라지지 않게 그래프에서 제거할 방법이 있어야 한다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 그래프의 노드 개수 $N$이 적힌 줄로 시작한다. 이어서 $N$개의 줄이 주어지며, 각 줄에는 정수 $N$개가 들어 있다. $i$번째 줄의 $j$번째 값 $L_{i,j}$는 $i$번째 노드와 $j$번째 노드를 끝점으로 하는 막대기의 길이이며, 그런 막대기가 없으면 0이다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 위에서 설명한 유효한 부분집합의 개수이다.

$1 \le T \le 100$. 모든 $i, j$에 대해 $0 \le L_{i,j} \le 1000$. 모든 $i$에 대해 $L_{i,i} = 0$. 모든 $i, j$에 대해 $L_{i,j} = L_{j,i}$.