Count Pairs Divisible by K

You are given an array of integers and an integer k. Your task is to determine the number of pairs (i, j) (with i < j) such that the sum of the pair is divisible by k. Formally, count the number of pairs satisfying:

\( (array[i] + array[j]) \mod k = 0 \)

This problem requires careful counting of remainders and applying combinatorial formulas. For example, if both numbers in the pair are divisible by k, they contribute to the count based on their frequency, and similarly for complementary remainders.

inputFormat

The input begins with an integer t (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 and k is the divisor. The next line contains n space-separated integers representing the array.

outputFormat

For each test case, output a single line containing the number of pairs whose sum is divisible by k.

## sample

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

4
2
3

</p>