도시 관광

Albert는 방학 동안 $N$개의 도시를 방문할 계획이다. 편의상 도시에는 1번부터 $N$번까지 번호가 붙어 있다. $N$개의 도시는 기차, 비행기, 유람선, 버스 등 여러 교통수단으로 연결되어 있다. 교통수단도 $N$개가 있으며, 편의상 1번부터 $N$번까지 번호가 붙어 있다.

$D_{k,i,j}$는 도시 $i$에서 도시 $j$로 $k$번째 교통수단을 타고 이동할 때 걸리는 시간이다. 이 값이 0이면 해당 교통수단으로는 $i$에서 $j$로 이동할 수 없다. 항상 $D_{k,i,j} = D_{k,j,i}$이다.

예를 들어 $N = 3$이고, $D_{1,\cdot,\cdot} = [[0, 1, 3], [1, 0, 4], [3, 4, 0]]$, $D_{2,\cdot,\cdot} = [[0, 2, 2], [2, 0, 4], [2, 4, 0]]$, $D_{3,\cdot,\cdot} = [[0, 3, 8], [3, 0, 4], [8, 4, 0]]$이라 하자.

• $D_{1,1,2} = 1$이므로 1번 교통수단으로 도시 1에서 도시 2로 가면 1 단위 시간이 걸린다.
• $D_{2,3,1} = 2$이므로 2번 교통수단으로 도시 3에서 도시 1로 가면 2 단위 시간이 걸린다.
• $D_{3,2,3} = 4$이므로 3번 교통수단으로 도시 2에서 도시 3으로 가면 4 단위 시간이 걸린다.

여러 교통수단과 일정을 알아보던 Albert는 1번 도시에서 출발해 각 교통수단을 정확히 한 번씩 이용하고, 각 도시를 정확히 한 번씩 방문한 뒤 1번 도시로 돌아오는 방법 중 가장 적게 걸리는 경우와 가장 오래 걸리는 경우를 알고 싶어 한다.

위 예제에서 도시 1 -> 도시 2 -> 도시 3 -> 도시 1로 이동하는 방법을 생각해 보자.

• 교통수단을 1, 2, 3 순서로 쓰면 $D_{1,1,2} + D_{2,2,3} + D_{3,3,1} = 1 + 4 + 8 = 13$ 단위 시간이 걸린다.
• 교통수단을 1, 3, 2 순서로 쓰면 $D_{1,1,2} + D_{3,2,3} + D_{2,3,1} = 1 + 4 + 2 = 7$ 단위 시간이 걸린다. 이 예제에서 가장 적게 걸리는 방법이다.
• 교통수단을 2, 1, 3 순서로 쓰면 $D_{2,1,2} + D_{1,2,3} + D_{3,3,1} = 2 + 4 + 8 = 14$ 단위 시간이 걸린다. 이 예제에서 가장 오래 걸리는 방법이다.
• 그 밖의 순서로도 각 교통수단을 한 번씩 이용하고 각 도시를 한 번씩 방문해 돌아올 수 있다.

위 예제의 답은 7과 14이다. 정수 $N$과 3차원 배열 $D$가 주어질 때, 위 조건을 만족하며 관광할 때 걸리는 최소 시간과 최대 시간을 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 $N$이 주어진다. 이어서 $N^2$개의 줄에 각 줄마다 공백으로 구분된 정수 $N$개가 주어진다. 처음 $N$개의 줄은 1번 교통수단의 $D_{1,\cdot,\cdot}$이며, 첫 줄은 $i = 1$, 다음 줄은 $i = 2$인 경우이다. 그다음 $N$개의 줄은 2번 교통수단의 값이며, 이런 식으로 $N$번 교통수단까지 순서대로 주어진다.

각 테스트 케이스마다 최소 시간과 최대 시간을 공백으로 구분해 한 줄에 출력한다. 조건을 만족하는 방법이 없으면 "0 0"을 출력한다.

• $1 \le T \le 10$
• $2 \le N \le 8$
• 모든 $1 \le i, j, k \le N$에 대해 $0 \le D_{k,i,j} \le 10^6$
• 모든 $1 \le i, j, k \le N$에 대해 $D_{k,i,j} = D_{k,j,i}$가 보장된다.
• 모든 $1 \le i, k \le N$에 대해 $D_{k,i,i} = 0$이 보장된다.