Given a sequence of integers a1, a2, ..., an and an integer m.

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 m.

Find the number of good subsequences of the sequence a.

Input

The first line contains the number of test cases t. The first line of each test case contains two space-separated integers n (1 ≤ n ≤ 30) and m (1 ≤ m ≤ 1000). The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1000).

Output

For each test case, print a single line containing one integer - the number of good subsequences.