有向无环图的拓扑排序是其顶点的一个排列 $p_1, \dots, p_n$，使得对于每一条弧，其起点在排列中出现在终点之前。

给定一个有向无环图。对于每一对顶点 $(u, v)$，计算满足顶点 $u$ 在顶点 $v$ 之前的拓扑排序的数量。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量。接下来是 $t$ 个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$：顶点数和弧数 ($1 \le n \le 20$, $0 \le m \le n \cdot (n - 1)/2$)。

接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$，表示从顶点 $u_i$ 到顶点 $v_i$ 的弧 ($1 \le u_i < v_i \le n$)。

输入中最多包含 100 个测试用例。其中 $n > 10$ 的测试用例不超过 5 个。

输出格式

对于每个测试用例，输出 $n$ 行，每行 $n$ 个数字。第 $i$ 行的第 $j$ 个数字应等于顶点 $j$ 在顶点 $i$ 之前的拓扑排序数量。特别地，当 $i = j$ 时，该值应为 0。

样例

输入格式 1

2
3 2
1 2
1 3

输出格式 1

0 0 0
2 0 1
2 1 0

输入格式 2

4 2
1 2
3 4

输出格式 2

0 0 3 1
6 0 5 3
3 1 0 0
5 3 6 0