#1214 외판원 순회 문제

52  1 s   128 MB  

Description

여러 개의 도시와 그 도시 간의 거리가 주어졌을 때, $1$번 도시 부터 출발하여 각 도시를 정확히 한 번씩 방문하고, 다시 $1$번 도시로 도착하였을 때 걸리는 시간이 가장 짧은 경로를 찾는 프로그램을 작성하라.

여기서 시간이란 거쳐가는 도시의 거리의 합을 뜻한다.

Input

입력의 첫 줄에는 테스트 케이스의 수 $T$ $(1 \leq T \leq 50)$이 주어진다.

각 테스트 케이스의 첫 줄에는 도시의 수 $N$ $(3 \leq N \leq 8)$ 이 주어진다.

그 후 $N$개의 줄에, 각각 $N$개씩의 도시간의 거리가 주어진다. 도시들은 $1$부터 $N$까지의 숫자로 표현되며, $i$번째 줄의 $j$번째 숫자는 $i$번째 도시와 $j$번째 도시 사이의 거리이다.

각 거리는 $1$ 이상 $100$이하의 정수이다. 만약 거리가 $0$일 경우는 해당 $i$번째 도시에서 $j$번째 도시로 직접 거쳐가는 경로가 존재하지 않음을 뜻한다.

Output

테스트 케이스마다 한 줄에 최소 경로의 길이를 출력한다.

만약 문제의 조건을 만족하지 못하는 경우 -1을 출력한다.

Sample Input

Sample Output

1
3
0 1 0
0 0 1
1 0 0
3