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을 도와 $1$부터 $n$까지 번호가 매겨진 $n$개의 정점을 가진 무방향 단순 그래프 $G$를 구성하세요.

$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$입니다. 가능한 해가 여러 개인 경우, 그중 아무것이나 출력하세요.

예제

입력 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

참고

실제 입력 행렬에서는 두 정수 사이에 공백이 하나만 있습니다. 예제에 있는 추가 공백은 레이아웃의 가독성을 높이기 위해 넣은 것입니다.