Problem Description
ZZX has a sequence a[1..n], which is a permutation of 1,2,...,n.
Now ZZX wants to perform some modifications on this sequence: every time he can choose a pair of integers i,j, satisfying 1<=ia[j], then swap a[i] and a[j].
If a permutation b[1..n] can be obtained by performing some modifications (possibly nothing is performed) on the initial sequence a, then ZZX says b is reachable from a.
Now JRY has m sequences a_1[1..n], a_2[1..n], ..., a_m[1..n]. Each of them is a permutation of 1,2,...,n. He wants to know how many pairs of (i,j) (1<=i<=m,1<=j<=m) satisfy a_i is reachable from a_j.
Input
First line contains an integer t. Then t testcases follow.
In each testcase: First line contains two integers n and m. Next m lines, each contains n integers a_i[1],a_i[2],...,a_i[n].
a_i is a permutation of 1,2,...,n.
There are at most 1000 small testcases and 1 big testcase. Small testcases satisfy 1<=n<=5 and 1<=m<=500. Big testcase satisfies 1<=n<=9, 1<=m<=300000.
Output
For each testcase print one integer as your answer in a line.
Sample Input
2
3 3
1 2 3
3 1 2
2 3 1
2 2
1 2
1 2
Sample Output
5
4