All Pairs Maximum Flow

Input: Standard Input

Output: Standard Output

"We must respect the other fellow's religion, but only in the sense and to the extent that we respect his theory that his wife is beautiful and his children smart."

H. L. Mencken

Given a square, symmetric matrix of edge capacities, return a squre, symmetric matrix of maximum flows.

In other words, you have n nodes. Between each pair of nodes, there is a pipe of a certain thickness (measured in liters per second, possibly zero). For each pair of nodes, (A, B), return the the maximum speed at which fluid can be pushed from node A to node B, in liters per second. Note that the flow for each pair of nodes is maximized separately -- there is no need to push all n² flows simultaneously.

Input

The first line of input gives the number of cases, N. N test cases follow. Each one starts with a line containing n (0 ≤ n ≤ 200). The next n lines will each contain n integers (between 0 and 10000 (inclusive)).

Output

For each test case, output one line containing "Case #x:" followed by n lines with n integers each. The diagonal should of this matrix should contain only zeroes.

Sample Input Output for Sample Input

0 2

2 0

0 1 1 0 1 0

1 0 0 1 0 1

1 0 0 1 0 0

0 1 1 0 0 0

1 0 0 0 0 1

0 1 0 0 1 0

Case #1:

0 2

2 0

Case #2:

0 3 2 2 2 2

3 0 2 2 2 2

2 2 0 2 2 2

2 2 2 0 2 2

2 2 2 2 0 2

2 2 2 2 2 0

Case #3:

Case #4:

Problemsetter: Igor Naverniouk

Special Thanks: Per Austrin