Cuber QQ has recently been interviewed for a job position. The interviewer challenged him with the following problem.

Given a multi-dimensional space with independent dimensions, the -th () of which has possible values . Write a random sampler to sample from this multi-dimensional space. Specifically, each time when the sampler is invoked, the sampler returns a tuple of length , , where . In additional, the new sample must never collide with any sample generated in the history, until the whole space is exhausted.

Cuber QQ had just learned usages of random library. He thought of this problem as a piece of cake, and wrote the following code. (It's a pseudo-code, in Python style.)

def sample(a: list[int]) -> list[int]:
    return [randint(0, a[i] - 1) for i in range(len(a))]

However, the interviewer looked at this code and quickly pointed out that he did not think of the cases where the samples could collide. That is, when you call \texttt{sample(a)} repeated, it will possibly yield duplicated samples. To convince Cuber QQ of this flaw, he tested Cuber QQ's program on a test data, which calls \texttt{sample} by times. The tester will count the number of violations of the "never collide" principle.

Specifically, the calls of sample return a list of arrays of length , where the -th element is denoted as (, ). For , the two arrays ``collide'' if holds for all . The tester will count the number of pairs where collision happens.

After the interview ends, Cuber QQ is curious about how this tester works. Your task is to help Cuber QQ implement this tester that counts collision.

The first line is one integer  (), which is the number of test cases.

For each test case, the first line are two integers ,  (, ).

The second line are  integers  ().

Then followed by  lines, the -th of which contains  integers  (). These are  lines of the output of Cuber QQ's program.

The sum of all  is no more than .

For each test case, output a number, which is the number of violations of "no collision".

3
2 3
2 2
0 1
0 0
0 1
3 2
3 2 3
2 0 1
0 0 1
2 3
42 3
4 2
4 2
4 2

1
0
3