Kamome sta attualmente studiando i cammini triangolari sui grafi non orientati pesati. Più specificamente, un cammino è detto triangolare se e solo se:

• La lunghezza di questo cammino non supera $2$, oppure
• Per qualsiasi terna di archi distinti $e_1$, $e_2$ ed $e_3$ su questo cammino, vale sempre che $w(e_1)$, $w(e_2)$ e $w(e_3)$ possono formare i tre lati di un triangolo.

Ricorda che gli interi positivi $x$, $y$ e $z$ possono formare i lati di un triangolo se e solo se $x < y + z$, $y < z + x$ e $z < x + y$.

Kamome ti ha fornito un grafo non orientato pesato. Devi determinare per ogni coppia di punti $(u, v)$ se esiste un cammino triangolare che parte da $u$ e termina in $v$. Assumiamo che esista sempre un cammino triangolare da ciascun nodo a se stesso.

Input

Ogni test contiene più casi di test. La prima riga contiene un intero $t$ ($1 \le t \le 10^5$), che indica il numero di casi di test. Segue la descrizione dei casi di test.

La prima riga contiene due interi $n, m$ ($1 \le n, m \le 3000$, $1 \le \sum n^2, \sum m^2 \le 3000^2$), che indicano il numero di nodi e di archi di questo grafo.

Le successive $m$ righe contengono ciascuna tre interi $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n$, $1 \le w_i \le 10^9$), che indicano un arco $(u_i, v_i)$ con peso $w_i$.

Il grafo può essere disconnesso o includere cappi (self-loop) o archi multipli.

Output

Per ogni caso di test, stampa $n$ righe, ciascuna contenente una stringa di $n$ caratteri, dove il $j$-esimo carattere è $s_{i,j}$: 0 se non esiste alcun cammino triangolare che parte da $i$ e termina in $j$, e 1 altrimenti.

Esempi

Input 1

2
4 3
1 2 2
2 3 2
3 4 3
8 7
1 2 3
2 3 4
3 4 1
3 5 2
2 6 2
6 7 4
6 8 5

Output 1

1111
1111
1111
1111
11101110
11111111
11111111
01111000
11111000
11100111
11100111
01100111