ZZX 有一个序列 $a$，它是 $1, 2, \dots, n$ 的一个排列。现在 ZZX 想要对这个序列进行一些修改。对于每次修改，他可以选择一对满足 $1 \le i < j \le n$ 且 $a_i > a_j$ 的整数 $i$ 和 $j$，然后交换 $a_i$ 和 $a_j$。

如果一个排列 $b$ 可以通过对初始序列 $a$ 进行若干次（可能是零次）修改得到，那么 ZZX 就称 $b$ 是从 $a$ 可达的。

现在 JRY 有 $m$ 个序列 $a^{(1)}, a^{(2)}, \dots, a^{(m)}$。它们中的每一个都是 $1, 2, \dots, n$ 的一个排列。他想知道有多少对 $(i, j)$（满足 $1 \le i \le m$ 且 $1 \le j \le m$）满足 $a^{(i)}$ 是从 $a^{(j)}$ 可达的。

输入格式

第一行包含一个整数 $T$。接下来是 $T$ 组测试数据。对于每组测试数据：

第一行包含两个整数 $n$ 和 $m$。接下来有 $m$ 行。其中第 $k$ 行包含 $n$ 个整数 $a^{(k)}_1, a^{(k)}_2, \dots, a^{(k)}_n$。每个 $a^{(k)}$ 都是 $1, 2, \dots, n$ 的一个排列。

最多有 1000 个小测试用例和 1 个大测试用例。小测试用例满足 $1 \le n \le 5$ 且 $1 \le m \le 500$。大测试用例满足 $1 \le n \le 9$ 且 $1 \le m \le 3 \cdot 10^5$。

输出格式

对于每组测试数据，在单独的一行中输出答案。

样例

输入样例 1

2
3 3
1 2 3
3 1 2
2 3 1
2 2
1 2
1 2

输出样例 1

5
4