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$ жолдың әрқайсысында есептің шартында сипатталған $A$ матрицасын білдіретін, бос орын арқылы бөлінген $n$ бүтін сан $a_{ij}$ ($-1 \le a_{ij} \le \frac{(n-3)(n-2)}{2}$) берілген.

Барлық тесттер бойынша $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

Нақты кіріс матрицасында екі бүтін санның арасында тек бір ғана бос орын болады. Мысалдағы қосымша бос орындар тек орналасудың оқылуын жақсарту үшін берілген.