Kamome is currently researching triangular paths on weighted undirected graphs. More specifically, a path is called triangular if and only if:

• The length of this path is no more than $2$, or
• For any three different edges $e_1$, $e_2$, and $e_3$ on this path, it is always true that $w(e_1)$, $w(e_2)$, and $w(e_3)$ can form the three sides of a triangle.

Recall that positive integers $x$, $y$, and $z$ can form the sides of a triangle if and only if $x < y + z$, $y < z + x$, and $z < x + y$.

Kamome has provided you with a weighted undirected graph. You need to determine for each pair of points $(u, v)$ whether there exists a triangular path starting from $u$ and ending at $v$. We assume that there is always a triangular path from each node to itself.

Input

Each test contains multiple test cases. The first line contains one integer $t$ ($1 \le t \le 10^5$), indicating the number of test cases. The description of the test cases follows.

The first line contains two integers $n, m$ ($1 \le n, m \le 3000$, $1 \le \sum n^2, \sum m^2 \le 3000^2$), indicating the number of nodes and edges of this graph.

The next $m$ lines, each line contains three integers $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n$, $1 \le w_i \le 10^9$), indicating edge $(u_i, v_i)$ with weight $w_i$.

The graph may be disconnected or include self-loops or multiple edges.

Output

For each test case, output $n$ lines, each line containing a string of $n$ characters, where the $j$-th character is $s_{i,j}$: 0 if there is no triangular path starting from $i$ and ending at $j$, and 1 otherwise.

Examples

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