VegiCat は $n \times n$ の整数行列 $A = (a_{ij})$ を持っています。各 $1 \le i, j \le n$ について：

• $i = j$、$i = 1$、または $j = 1$ のとき、$a_{ij} = -1$ です。
• そうでないとき、$a_{ij}$ は非負整数です。

$1$ から $n$ までの番号が付けられた $n$ 個の頂点を持つ無向単純グラフ $G$ を構築して、VegiCat を助けてください。

$i > 1$ かつ $j > 1$ を満たす相異なる頂点の各組 $i, j$ について、グラフは次の条件を満たさなければなりません：頂点 $i$ と $j$、およびそれらのいずれかを端点に持つすべての辺を削除した後、ちょうど $a_{ij}$ 本の辺が残る。

頂点の各組 $i, j$ は個別に考えます。つまり、それぞれの組について、頂点や辺が一切削除される前のグラフ $G$ から考えます。

このようなグラフが少なくとも 1 つ存在することが保証されています。解が複数存在する場合は、そのうちのどれを出力しても構いません。

入力

1 行目にはテストケースの個数を表す整数 $T$（$1 \le T \le 6 \cdot 10^4$）が与えられます。続いて各テストケースが与えられます。

各テストケースの 1 行目には、グラフの頂点数を表す整数 $n$（$4 \le n \le 10^3$）が与えられます。

続く $n$ 行には、問題文で説明された行列 $A$ を表す $n$ 個の空白区切りの整数 $a_{ij}$（$-1 \le a_{ij} \le \frac{(n-3)(n-2)}{2}$）がそれぞれ与えられます。

すべてのテストケースにわたる $n^2$ の総和は $1.2 \cdot 10^6$ を超えず、行列 $A$ に対応するグラフが少なくとも 1 つ存在することが保証されています。

出力

各テストケースについて、構築したグラフの隣接行列を出力してください。それぞれ $n$ 個の空白区切りの整数を含む $n$ 行を出力してください。各整数は $0$ または $1$ でなければなりません。$i$ 行目 $j$ 列目の要素は、頂点 $i$ と頂点 $j$ の間に辺がある場合は $1$、そうでない場合は $0$ です。解が複数存在する場合は、そのうちのどれを出力しても構いません。

入出力例

入力 1

2
5
-1 -1 -1 -1 -1
-1 -1  3  1  2
-1  3 -1  2  2
-1  1  2 -1  1
-1  2  2  1 -1
7
-1 -1 -1 -1 -1 -1 -1
-1 -1  4  5  3  6  5
-1  4 -1  5  4  5  5
-1  5  5 -1  5  7  5
-1  3  4  5 -1  4  4
-1  6  5  7  4 -1  5
-1  5  5  5  4  5 -1

出力 1

0 1 0 1 1
1 0 0 0 0
0 0 0 1 0
1 0 1 0 1
1 0 0 1 0
0 1 1 0 1 0 0
1 0 0 0 0 1 1
1 0 0 0 1 0 1
0 0 0 0 1 1 0
1 0 1 1 0 0 1
0 1 0 1 0 0 0
0 1 1 0 1 0 0

注記

実際の入力行列では、2 つの整数の間には空白が 1 つだけあります。入出力例の余分な空白は、レイアウトの視認性を高めるためのものです。