19469번 - Reachable Sequences 다국어

문제

ZZX has a sequence $a,ドル which is a permutation of 1,ドル 2, \ldots, n$. Now ZZX wants to perform some modifications on this sequence. For each modification, he can choose a pair of integers $i$ and $j,ドル satisfying 1ドル \le i < j \le n$ and $a_i > a_j,ドル and then swap $a_i$ and $a_j$.

If a permutation $b$ can be obtained by performing some (possibly zero) modifications on the initial sequence $a,ドル then ZZX says $b$ is reachable from $a$.

Now JRY has $m$ sequences $a^{(1)},ドル $a^{(2)},ドル $\ldots,ドル $a^{(m)}$. Each of them is a permutation of 1,ドル 2, \ldots, n$. He wants to know how many pairs $(i, j)$ such that 1ドル \le i \le m$ and 1ドル \le j \le m$ have the property that $a_i$ is reachable from $a_j$.

입력

The first line contains an integer $T$. Then $T$ test cases follow. In each test case:

The first line contains two integers $n$ and $m$. After that, $m$ lines follow. The $k$-th of them contains $n$ integers $a^{(k)}_1,ドル $a^{(k)}_2,ドル $\ldots,ドル $a^{(k)}_n$. Each $a^{(k)}$ is a permutation of 1,ドル 2, \ldots, n$.

There are at most 1000ドル$ small test cases and 1ドル$ large test case. The small test cases satisfy 1ドル \le n \le 5$ and 1ドル \le m \le 500$. The large test case satisfies 1ドル \le n \le 9$ and 1ドル \le m \le 3 \cdot 10^5$.

출력

For each test case, print the answer on a separate line.

제한

힌트