You are given set of N vectors, each vector consists of K integers. Vector ex equals ey iff there exists function bijection f and integer r, such that ex[i] = f( ey[(i+r)%K] ), for each i in range [0, K> Eg. (1, 2, 2, 3) == (22, 3, 4, 22), with r=2 and f(22)=2, f(3)=3 and f(4)=1. But (22,3,22,4) is not equal to (1, 2, 2, 3).

How many different vectors are there in set of N given vectors?

Constraints:

n <= 10000

k <= 100

vector values are from range [0, 10^9]

Input

First number contains T (T <= 10), number of test cases. Each test cases consists of following. First line consists of N and K. N lines follows, the i-th containing K integers describing i-th vector.

Output

Output one number, number of different vectors.

Input:
2
3 4
22 3 4 22
1 2 2 3
22 3 22 4
5 5
3 3 3 0 3
8 4 4 4 0
1 1 1 1 1
1 1 8 6 1
1 3 3 3 5

Output:
2
3