Trong tựa game Yasuo, có \(n\) con boss, mỗi con boss có lượng máu riêng của chúng. Con boss thứ \(i\) có lượng máu là \(h_i\).

Ban đầu, khi chưa tiêu diệt được con boss nào, nhân vật chính sẽ có thanh katana "Trăn Trối". Với mỗi nhát chém, thanh gươm gây \(1\) sát thương cho mỗi con boss bất kỳ.

Sau khi tiêu diệt được con boss thứ \(i\) bạn sẽ nhận "THÊM" một thanh katana mới, thanh gươm này sẽ gây \(a[i][j]\) sát thương một nhát chém đối với con boss thứ \(j\).

Lưu ý: các thanh gươm trước đó không bị mất đi, vẫn có thể được sử dụng tiếp.

Hãy tìm số nhát chém tối thiểu để "phá đảo" trò chơi.

Input

• Số nguyên dương \(q\) --- số câu hỏi
• Mỗi câu hỏi chứa số nguyên dương \(n\), máu của \(n\) boss \(h_1, h_2, ..., h_n\) và ma trận \(a\)

Constraints

• \(q \leq 40\)
• \(n \leq 15\)
• \(1 \leq h_i \leq 10^6\)
• \(0 \leq a[i][j] \leq 9\)

Output

• Với mỗi test case, in ra một dòng theo định dạng Case X: Y trong đó \(X\) là số thứ tự test case và \(Y\) là số nhát chém tối thiểu

Example

2
3
10 10 10
010
100 
111
3
3 5 7
030
500
007

Case 1: 30
Case 2: 12

Tham khảo: LightOJ