每一个置换 $\sigma$ 都可以与自身复合，即 $\sigma^2 = \sigma \circ \sigma$。更一般地，对于正整数 $k$，$\sigma^k = \sigma \circ \sigma^{k-1}$，且 $\sigma^0$ 为恒等置换。对于一个置换 $\sigma$，其所有复合构成的集合称为 $D(\sigma)$，即 $D(\sigma) = \{\sigma^k : k \in \mathbb{N}\}$。

给定一个包含 $m$ 个 $n$ 阶置换的序列 $\sigma_1, \sigma_2, \dots, \sigma_m$。对于每个 $i$，求满足 $D(\sigma_i) = D(\sigma_j)$ 的 $j < i$ 的个数。

输入格式

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

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 10^2, 1 \le m \le 10^4$)。

在接下来的 $m$ 行中，每行给出一个置换，表示为 $n$ 个不同的正整数序列 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)。

输出格式

对于每个测试用例，输出 $m$ 行，每行一个数字，表示满足给定条件的 $j$ 的个数。

样例

样例输入 1

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

样例输出 1

0
1
0