Kamome 目前正在研究带权无向图上的三角形路径。更具体地，一条路径被称为三角形路径，当且仅当：

• 该路径的长度不超过 2，或
• 对于该路径上的任意三条不同边 $e_1, e_2, e_3$，总是满足 $w(e_1), w(e_2), w(e_3)$ 能构成一个三角形的三条边。

回想一下，正整数 $x, y, z$ 能构成三角形的三条边当且仅当 $x < y + z$、$y < z + x$ 且 $z < x + y$。

Kamome 给出了一个带权无向图。你需要对于每对点 $(u, v)$，判断是否存在一条从 $u$ 出发到 $v$ 结束的三角形路径。我们假设每个节点到其自身总是存在一条三角形路径。

图 1：北京大学“三角地”的一部分

输入格式

每个测试点包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n, m$（$1 \le n, m \le 3000$，$1 < \sum n^2, \sum m^2 \le 3000^2$），表示该图的节点数和边数。

接下来的 $m$ 行，每行包含三个整数 $u_i, v_i, w_i$（$1 \le u_i, v_i \le n$，$1 < w_i \le 10^9$），表示权值为 $w_i$ 的边 $(u_i, v_i)$。

图可能不连通，或者包含自环或重边。

输出格式

对于每个测试用例，输出 $n$ 行，每行包含一个由 $n$ 个字符组成的字符串，其中第 $j$ 个字符为 $s_{i,j}$。如果为 '0' 表示不存在从 $i$ 到 $j$ 的三角形路径，否则为 '1'。

样例

输入格式 1

2
4 3
1 2 2
1 2 2
2 3 2
3 2
1 2 3
2 3 2
3 4 3

输出格式 1

1111
1111
1111
1111
11101110
11111111

输入格式 2

3 2
1 2 3
2 3 4
3 4 1

输出格式 2

01111000
11111000
11100111

输入格式 3

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

输出格式 3

11100111
01100111