Magic set#10273
Given a sequence of integers a_1, a_2, \ldots, a_n and an integer .
Lets define a **good sequence** of integers as a non-empty sequence such that the sum of the elements in each of its non-empty subsequences is divisible by .
Find the number of good subsequences of the sequence .
The first line contains the number of test cases . The first line of each test case contains two space-separated integers (1 \le n \le 30) and (1 \le m \le 1000). The second line contains integers a_1, a_2, \ldots, a_n (1 \le a_i \le 1000).
For each test case, print a single line containing one integer - the number of good subsequences.
Example 1