Kamome forskar för närvarande om triangulära vägar i viktade oriktade grafer. Mer specifikt kallas en väg triangulär om och endast om:

• Längden på denna väg är högst $2$, eller
• För varje tre olika kanter $e_1$, $e_2$ och $e_3$ på denna väg gäller alltid att $w(e_1)$, $w(e_2)$ och $w(e_3)$ kan bilda de tre sidorna i en triangel.

Kom ihåg att positiva heltal $x$, $y$ och $z$ kan bilda sidorna i en triangel om och endast om $x < y + z$, $y < z + x$ och $z < x + y$.

Kamome har gett dig en viktad oriktad graf. Du behöver avgöra för varje par av noder $(u, v)$ om det finns en triangulär väg som börjar i $u$ och slutar i $v$. Vi antar att det alltid finns en triangulär väg från varje nod till sig själv.

Indata

Varje test innehåller flera testfall. Den första raden innehåller ett heltal $t$ ($1 \le t \le 10^5$), som anger antalet testfall. Beskrivningen av testfallen följer.

Den första raden innehåller två heltal $n, m$ ($1 \le n, m \le 3000$, $1 \le \sum n^2, \sum m^2 \le 3000^2$), som anger antalet noder och kanter i denna graf.

De följande $m$ raderna innehåller var och en tre heltal $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n$, $1 \le w_i \le 10^9$), som anger en kant $(u_i, v_i)$ med vikt $w_i$.

Grafen kan vara osammanhängande eller innehålla egencykler (self-loops) eller multipla kanter.

Utdata

För varje testfall, skriv ut $n$ rader, där varje rad innehåller en sträng med $n$ tecken, där det $j$-te tecknet är $s_{i,j}$: 0 om det inte finns någon triangulär väg som börjar i $i$ och slutar i $j$, och 1 annars.

Exempel

Indata 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

Utdata 1

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