Largest Non-Divisible Subset

Given an array of positive integers and an integer \(K\), your task is to find the size of the largest subset such that the sum of any two numbers in the subset is not divisible by \(K\). For two elements \(a\) and \(b\) in the subset, it must hold that \( (a+b) \mod K \neq 0\).

Input: The first line contains an integer \(T\) denoting the number of test cases. For each test case, the first line contains two integers \(N\) and \(K\), where \(N\) is the number of elements in the array. The second line contains \(N\) space-separated integers representing the elements of the array.

Output: For each test case, output a single number which is the size of the largest subset satisfying the above condition.

Note: Use standard input and output for reading and writing data.

inputFormat

The input begins with an integer \(T\) on a new line indicating the number of test cases. Then \(T\) test cases follow.

Each test case consists of two lines:

• The first line contains two integers \(N\) and \(K\) separated by a space.
• The second line contains \(N\) integers separated by spaces representing the array elements.

outputFormat

For each test case, print one integer representing the size of the largest subset where the sum of any two elements is not divisible by \(K\). Each result should be printed on its own line.

## sample

4
4 3
1 7 2 4
5 5
3 5 10 15 20
3 2
2 4 6
5 4
1 3 2 6 8

3
2
1
3

</p>