permu

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<=i<j<=n and a[i]>a[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

Author

学军中学

Source

2016 Multi-University Training Contest 8