2550. Determinatron

Partychen likes linear algebra. He’s a master of computing determinants and permanents of square matrices. Now he has come up with a matrix property of his own. He calls it the determinatron.

Take any n-by-n matrix M. We will use the following matrix as an example.

 1 2 3 4 5 6 7 8 0

Consider each possible way of selecting n entries from the matrix without taking more than 1 entry from the same row or the same column. For each such selection, add the numbers in the selected locations. In our example, these are the possible selections and their sums.

 1 + 5 + 0 = 6 1 + 8 + 6 = 15 4 + 2 + 0 = 6 4 + 8 + 3 = 15 7 + 2 + 6 = 15 7 + 5 + 3 = 15 Total: 72

The determinatron is the sum of all these sums. In our example, it is equal to 72. Your task is to write a program to help Sam compute determinatrons.

输入格式

The first line of input gives the number of cases, N. N test cases follow. Each one starts with a line containing n. The next n lines each contain n integers.

1 ≤ N ≤ 100;

1 ≤ n ≤ 20;

All matrix entries will be between -100 and 100, inclusive;The answer will always fit into a 32-bit signed integer.

输出格式

For each test case, output a single line of the form “Case #x: y”, where x is the test case number and y is the determinatron of the given matrix.

样例

Input
4
3
1 2 3
4 5 6
7 8 0
3
1 2 3
4 5 6
7 8 9
4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
2
-4 4
3 3

Output
Case #1: 72
Case #2: 90
Case #3: 0
Case #4: 6


17 人解决，78 人已尝试。

28 份提交通过，共有 286 份提交。

7.5 EMB 奖励。