Count Divisible Subsequences

You are given a sequence of integers and an integer \(K\). Your task is to count the number of non-empty subsequences (i.e., subsets) whose sum is divisible by \(K\). In other words, for each test case you need to find the number of ways to choose some elements from the sequence (at least one) such that the sum of these chosen elements is a multiple of \(K\).

The input begins with an integer \(T\) denoting the number of test cases. Then, for each test case, the first line contains two integers \(N\) and \(K\) where \(N\) is the number of elements in the sequence, and the second line contains \(N\) space-separated integers. For each test case, output the count of subsequences meeting the requirement on a new line.

Note: Since the number of subsequences grows exponentially with \(N\), you may assume that \(N\) is small enough for a brute force solution to work.

inputFormat

The first line contains an integer \(T\) representing the number of test cases. Each test case consists of two lines:

• The first line contains two integers \(N\) and \(K\) where \(N\) is the length of the sequence and \(K\) is the divisor.
• The second line contains \(N\) space-separated integers representing the sequence.

outputFormat

For each test case, print a single line containing the number of non-empty subsequences whose sum is divisible by \(K\).

## sample

1
3 3
3 6 9

7

</p>