Last week, we helped HCMUS to calculate their data transfer rate among their \(N\) servers. Their system works so well and become a model for other universities to follow. The Danang University of Technology (DUT) wants to build the same system.

DUT already have \(N\) servers, they want to connect them using bi-directional cables. Each pair of servers is connected by at most 1 cable (possibly 0).

The cable connecting server \(u\) and server \(v\) has the transmission capacity of \(C_{u,v}\) megabits per nanosecond. Let us define \(F_{u,v}\) as the data transfer rate between server \(u\) and server \(v\). To transfer data from server \(u\) to server \(v\), data can be split into multi parts and transferred via multiple routes.

For example, to transfer data from server 1 to server 4, data can be split into 3 parts and transferred via 3 routes as follows:

• 1 - 4 (30 Mb per nanosecond)
• 1 - 3 - 4 (20 Mb per nanosecond)
• 1 - 2 - 4 (10 Mb per nanosecond)

so the transfer rate from 1 to 4 is 60 Mb per nanosecond or \(F_{1,4} = 60\).

DUT has their expected data transfer rate F, your task is to help them select the cables and how to connect the N servers to achieve that expected transfer rate F. There might be multiple configurations to achieve that.

Input

• The first line is \(T\) the number of test cases. Then \(T\) test cases follow.
• Each test case starts with an integer \(N\) \((N \leq 200)\).
• In the next \(N\) lines, each contains \(N\) integers to describe 2D array \(F\).
• It is guarantee that \(F_{u,v} = F_{v,u}\), \(F_{u,u} = 0\), \(0 \leq F_{u,v} \leq 10^6\).
• The sum of \(N\) in all test cases does not exceed 1000.

Output

• Each test case should start with a line containing: Case #t: YES or Case #t: NO if it is possible/impossible to achieve the expected data transfer rate \(F\).
• If it is possible, the next \(N\) lines should describe your configuration.
• The \(v^{th}\) number of the \(u^{th}\) row should represent \(C_{u,v}\).
• You have to make sure that \(C_{u,v} = C_{v,u}\), \(C_{u,u} = 0\) and \(0 \leq C_{u,v} \leq 10^6\).

Example

2
3
0 1 2
1 0 4
2 4 0
4
0 60 60 60
60 0 60 60
60 60 0 90
60 60 90 0

Case #1: NO
Case #2: YES
0 30 30 0
30 0 30 0
30 30 0 90
0 0 90 0