요정과 마녀

Pari는 Fairyland를 사악한 마녀들로부터 지키기 위해 싸우는 강력한 요정이다. 마녀들은 날마다 더욱 강력해지고 있으므로, Pari는 마법 막대를 사용해 보호 주문을 걸어야 한다. 막대들을 넓이가 양수인 볼록 다각형을 이루도록 배치하면 그렇게 할 수 있다.

하지만 Pari가 원하는 막대를 반드시 마음대로 사용할 수 있는 것은 아니다! Fairyland에서 사용할 수 있는 모든 막대는 함께 묶여 있으며, 간선이 막대이고 정점이 하나 이상의 막대의 끝점인 그래프를 이룬다. (막대들은 끝점 이외의 곳에서는 절대 서로 닿지 않는다. 마법의 막대이기 때문이다!) Whenever Pari 막대를 하나 꺼내 주문에 사용하면, 그 막대와 인접했던 모든 막대(즉, 그 막대와 정점을 공유했던 막대)는 영원히 사라져 이후에는 사용할 수 없다.

Pari는 그래프에서 꺼내어 넓이가 양수인 볼록 다각형을 만드는 데 사용할 수 있는 서로 다른 막대 부분집합이 몇 개인지 궁금하다. 길이가 같은 막대들도 모두 서로 다른 것으로 간주한다. 두 막대 부분집합은 한 부분집합에는 있지만 다른 부분집합에는 없는 막대가 적어도 하나 있을 때, 그리고 그럴 때에만 서로 다르다. 위에서 설명했듯이, 어떤 부분집합에 속한 막대 중 어느 것도 사라지지 않게 그 부분집합의 모든 막대를 그래프에서 꺼낼 방법이 있는 경우에만 그 부분집합은 유효하다.

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 40초. 메모리 제한: 1 GB. 모든 i, j에 대해 0 ≤ $L_{i, j}$ ≤ 1000. 모든 i에 대해 $L_{i, i}$ = 0. 모든 i, j에 대해 $L_{i, j}$ = $L_{j, i}$.

작은 데이터 세트

N = 6.

큰 데이터 세트

6 ≤ N ≤ 15.

입력의 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 막대들이 이루는 그래프의 정점 수를 나타내는 정수 N 하나가 포함된 한 줄로 시작한다. 이어서 N개의 줄이 주어지며, 각 줄에는 N개의 정수 $L_{i, j}$가 포함된다. i번째 줄의 j번째 값은 i번째 정점과 j번째 정점을 끝점으로 하는 막대의 길이를 나타내며, 그러한 막대가 없으면 0이다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 위에서 설명한 유효한 부분집합의 수이다.

예제 케이스 #1에서 묶음 그래프에는 길이가 같은 간선이 5개 있으며, 이들을 연결하는 정점으로 나타내면 1-2, 2-3, 3-4, 4-5, 5-6이다. 닫힌 다각형을 만들려면 변이 적어도 3개 필요하지만, 막대 3개를 꺼낼 수 있는 유일한 방법은 막대 1-2, 3-4, 5-6을 선택하는 것이다.

예제 케이스 #2에서 그래프에는 막대 3개, 즉 1-2, 3-4, 5-6이 있다. 그래프가 연결되어 있지 않을 수도 있음에 유의한다. 변의 길이가 2, 3, 4인 삼각형을 만들 수 있다.

예제 케이스 #3에서 그래프에는 막대 3개, 즉 1-2, 3-4, 5-6이 있다. 하지만 길이가 1,2, 4인 막대를 사용해서는 닫힌 다각형을 만들 수 없다.

예제 케이스 #4에서는 막대를 1개보다 많이 꺼낼 수 없다.

추가 예제 - 테스트 세트 2

예제 케이스 #1에서는 막대 4개가 모두 같은 길이이다. 삼각형을 만드는 방법은 4가지이고, 정사각형을 만드는 방법은 한 가지이다.