Một bàn cờ vua đặc biệt có \(n \times n\) ô vuông. Ô vuông ở hàng \(i\) cột \(j\) có giá trị nguyên dương là \(a[i][j]\).

Hãy tìm cách xếp \(n\) quân xe lên bàn cờ sao cho không có hai quân xe nào "ăn nhau" và tổng giá trị của các ô vuông có đặt quân xe là lớn nhất.

Input

• Số nguyên dương \(t\) --- số câu hỏi
• Mỗi câu hỏi chứa số nguyên dương \(n\), và ma trận \(a\)

Output

• Với mỗi câu hỏi, in ra một dòng có dạng Case k: x trong đó \(k\) là số thứ tự câu hỏi và \(x\) là tổng giá trị lớn nhất ở các ô vuông có đặt quân xe

Constraints

• \(t \leq 100\)
• \(n \leq 16\)
• \(1 \leq a[i][j] \leq 10^5\)

Example

2
2
1 5
2 1
3
1 2 3
6 5 4
8 1 2

Case 1: 7
Case 2: 16

Scoring

• \(40\%\) số điểm thỏa mãn \(n \leq 10\)