Watch Together

You are given data about several users and the movies each has watched. For each test case, you need to count the number of unordered pairs of users who have watched at least \(k\) common movies.

More formally, for each test case, you are given:

• An integer \(U\) representing the number of users.
• An integer \(M\) representing the total number of movies (provided for context, though it is not used in the computation).
• For each user, a user ID and the list of movies they have watched. Each movie is identified by an integer.
• An integer \(k\) which is the threshold for the number of common movies.

Your task is to determine, for each test case, the number of distinct pairs \((i, j)\) with \(i < j\) such that the users corresponding to \(i\) and \(j\) have at least \(k\) movies in common. The output for each test case should be a single integer on its own line.

Input/Output Format: The program should read from standard input (stdin) and write to standard output (stdout).

inputFormat

The first line contains a single integer \(T\), the number of test cases.

For each test case, the first line contains three integers \(U\), \(M\) and \(k\), where \(U\) is the number of users, \(M\) is the total number of movies available, and \(k\) is the minimum number of common movies required for a pair to be counted.

This is followed by \(U\) lines, each describing a user. Each of these lines begins with an integer representing the user's unique ID, followed by an integer \(L\) indicating the number of movies the user has watched, and then \(L\) integers representing the movie IDs.

Example:

4 5 2
1 3 1 2 3
2 2 1 2
3 2 2 3
4 2 4 5

This corresponds to a test case with 4 users, 5 movies in total, and a threshold \(k=2\). The first user (ID 1) has watched movies 1, 2, and 3, and so on.

outputFormat

For each test case, output a single integer on a new line representing the number of user pairs who have watched at least \(k\) common movies.

Example Output:

2

## sample

4
4 5 2
1 3 1 2 3
2 2 1 2
3 2 2 3
4 2 4 5
3 4 1
1 2 1 2
2 2 2 3
3 2 3 4
3 4 2
1 2 1 2
2 2 2 3
3 2 3 4
2 2 1
1 1 1
2 1 2

2
2
0
0

</p>