In this problem, we use the following graph theory definitions:

• A topological sort of a directed graph $G=(V,E)$ with $n$ vertices labeled $1, 2, \dots, n$ is a permutation $p$ of $1, 2, \dots, n$ such that for every edge $x \to y$ in $E$, $x$ appears before $y$ in $p$.

Today, the algorithm competition robot Little G learned about topological sorting. With its powerful machine learning capabilities, it quickly learned how to calculate the number of topological sorts for a directed acyclic graph (DAG). Then, it began to think about an extension: given a DAG $G$ and two vertices $u, v$ in $G$, find how many topological sorts of $G$ satisfy the condition that $u$ appears before $v$.

You know that with a little thought, Little G could solve this problem instantly. Unfortunately, the power went out, and Little G, which relies on a power plug, stopped working. Therefore, you have to solve this extension problem yourself.

To make the problem more challenging, given the total number of vertices $n$ in $G$, please find the answer for all $n(n-1)$ pairs $(u, v)$.

Input

This problem contains multiple test cases. The first line contains the number of test cases $T$.

For each test case: the first line contains two positive integers $n$ and $m$, representing the number of vertices and edges in $G$, respectively. The next $m$ lines each contain two positive integers $x$ and $y$, representing a directed edge $x \to y$ in the graph. It is guaranteed that there are no multiple edges and $x < y$ (which means $[1, 2, \dots, n]$ is always a valid topological sort).

It is guaranteed that in any single test case, there are at most $5$ test cases where $n > 10$.

Output

For each test case, output an $n \times n$ matrix where the element in the $i$-th row and $j$-th column is the answer for $v=i, u=j$. Note that the order of $(v, u)$ is the reverse of $(i, j)$. Specifically, when $i=j$, output $0$.

Examples

Input 1

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

Output 1

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

Note 1

For the first test case, the original graph has two topological sorts: $[1, 2, 3]$ and $[1, 3, 2]$. There are $2$ topological sorts where $1$ appears before $2$, so the element in the $2$-nd row and $1$-st column of the answer matrix is $2$. There is $1$ topological sort where $3$ appears before $2$, so the element in the $2$-nd row and $3$-rd column is $1$.

Examples 2/3

See the provided files.

Example $2$ satisfies the constraints of Subtask $1$.

Example $3$ satisfies the constraints of Subtask $10$.

Constraints

For all data: $1 \le T \le 100, 1 \le n \le 20, 0 \le m \le \binom n2$. It is guaranteed that in any single test case, there are at most $5$ test cases where $n > 10$.