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.

!!note: có ảnh

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 F1,4 = 60. In this example, the full
data transfer rate F is followed:

!!note: có ảnh

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, for example:

!!note: có ảnh

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 \le 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 \le F_{u,v} \le 1000000\).
• 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 \le C_{u,v} \le 1000000\).

Example

23
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