City Tour

Albert plans to visit $N$ cities during his vacation. For convenience, the cities are numbered 1 to $N$. The $N$ cities are connected by various transportation means such as trains, airplanes, cruise ships, and buses. There are also $N$ different transportation means, numbered 1 to $N$ for convenience.

$D_{k,i,j}$ is the time it takes to travel from city $i$ to city $j$ using the $k$-th transportation means. If this value is 0, the means cannot be used to travel from $i$ to $j$. It is always true that $D_{k,i,j} = D_{k,j,i}$.

For example, let $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]]$, and $D_{3,\cdot,\cdot} = [[0, 3, 8], [3, 0, 4], [8, 4, 0]]$.

• $D_{1,1,2} = 1$, so traveling from city 1 to city 2 by the 1st means takes 1 unit of time.
• $D_{2,3,1} = 2$, so traveling from city 3 to city 1 by the 2nd means takes 2 units of time.
• $D_{3,2,3} = 4$, so traveling from city 2 to city 3 by the 3rd means takes 4 units of time.

While looking into various transportation options and schedules, Albert wanted to know the shortest and longest times for a route that starts at city 1, uses each transportation means exactly once, visits each city exactly once, and then returns to city 1.

In the example above, consider the route city 1 -> city 2 -> city 3 -> city 1.

• Using the means in the order 1, 2, 3 takes $D_{1,1,2} + D_{2,2,3} + D_{3,3,1} = 1 + 4 + 8 = 13$ units of time.
• Using the means in the order 1, 3, 2 takes $D_{1,1,2} + D_{3,2,3} + D_{2,3,1} = 1 + 4 + 2 = 7$ units of time. This is the shortest route in this example.
• Using the means in the order 2, 1, 3 takes $D_{2,1,2} + D_{1,2,3} + D_{3,3,1} = 2 + 4 + 8 = 14$ units of time. This is the longest route in this example.
• Other orders also let Albert use each means once, visit each city once, and return.

For this example, the answers are 7 and 14. Given $N$ and the 3D array $D$, find the minimum and maximum times for such a tour.

The first line contains the number of test cases $T$.

Each test case starts with a line containing $N$. The next $N^2$ lines each contain $N$ integers separated by spaces. The first $N$ lines give $D_{1,\cdot,\cdot}$, where the first of these lines is for $i = 1$, the next is for $i = 2$, and so on. The next $N$ lines give the times for the 2nd means, and this continues in order up to the $N$-th means.

For each test case, print the minimum and maximum time on one line, separated by a space. If no tour satisfies the conditions, print "0 0".

• $1 \le T \le 10$
• $2 \le N \le 8$
• For all $1 \le i, j, k \le N$: $0 \le D_{k,i,j} \le 10^6$
• For all $1 \le i, j, k \le N$: $D_{k,i,j} = D_{k,j,i}$ is guaranteed.
• For all $1 \le i, k \le N$: $D_{k,i,i} = 0$ is guaranteed.