VegiCat 有一個 $n \times n$ 嘅整數矩陣 $A = (a_{ij})$。對於每個 $1 \le i, j \le n$：
- 如果 $i = j$、$i = 1$ 或者 $j = 1$，噉 $a_{ij} = -1$。
- 否則，$a_{ij}$ 係一個非負整數。
請幫 VegiCat 構造一個有 $n$ 個頂點嘅無向簡單圖 $G$，頂點由 $1$ 到 $n$ 編號。
對於每一對滿足 $i > 1$ 同埋 $j > 1$ 嘅唔同頂點 $i, j$，個圖都必須滿足以下條件：喺刪走頂點 $i$ 同 $j$，以及所有以呢兩個頂點其中之一作為端點嘅邊之後，啱啱好淨低 $a_{ij}$ 條邊。
每一對頂點 $i, j$ 係獨立考慮嘅。即係話，對於每一對頂點，都係由未刪走任何頂點或者邊之前嘅原圖 $G$ 開始。
題目保證至少存在一個符合條件嘅圖。如果有多個解，輸出邊一個都得。
輸入格式
第一行包含一個整數 $T$（$1 \le T \le 6 \cdot 10^4$），代表測試數據嘅組數。接住落嚟係各組測試數據嘅描述。
對於每組測試數據，第一行包含一個整數 $n$（$4 \le n \le 10^3$），代表圖入面嘅頂點數量。
接住落嚟嘅 $n$ 行，每行包含 $n$ 個用空格隔開嘅整數 $a_{ij}$（$-1 \le a_{ij} \le \frac{(n-3)(n-2)}{2}$），代表題目所講嘅矩陣 $A$。
題目保證所有測試數據入面 $n^2$ 嘅總和唔超過 $1.2 \cdot 10^6$，而且至少存在一個對應矩陣 $A$ 嘅圖。
輸出格式
對於每組測試數據，輸出你構造出嚟嘅圖嘅鄰接矩陣。輸出 $n$ 行，每行包含 $n$ 個用空格隔開嘅整數。每個整數必須係 $0$ 或者 $1$。如果頂點 $i$ 同頂點 $j$ 之間有一條邊，第 $i$ 行第 $j$ 列嘅數值就係 $1$，否則係 $0$。如果有多個解，輸出邊一個都得。
Examples
Input 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
Output 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
Note
實際輸入矩陣入面兩個整數之間只會有一個空格。範例入面額外嘅空格係為咗令版面更加易讀。