Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

Katya has a sequence of integers $a_{1}, a_{2}, \dots, a_{n}$ and an integer $m$.

She defines 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$.

Katya wants to know the number of good subsequences of the sequence $a$. Can you help her?

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $n$ and $m$.
The second line contains $n$ space-separated integers $a_{1}, a_{2}, \dots, a_{n}$.

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

------  Constraints  ------
$1 ≤ T ≤ 1,000$
$1 ≤ n ≤ 30$
$1 ≤ m ≤ 1,000$
$1 ≤ a_{i} ≤ 1,000$ for each valid $i$

------  Subtasks ------
Subtask #1 (30 points): $1 ≤ n ≤ 5$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
2
2 3
1 2
2 3
1 3
----- Sample Output 1 ------ 
0
1
----- explanation 1 ------ 
Example case 1: There are no good subsequences.

Example case 2: There is exactly one good subsequence of $a$: $[3]$.

Difficulty: MEDIUM
Tags: Combinatorics

Mathematics

Starter code:

Solutions:
a = int(input())
cnt = 0
for i in range(a):
	(x, y) = map(int, input().split())
	ar = list(map(int, input().split()))
	for i in ar:
		if i % y == 0:
			cnt += 1
	print(2 ** cnt - 1)
	cnt = 0


ro = 50
k = 100
p = int(input())
for _ in range(p):
	count = 0
	(n, n1) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	for i in a:
		if i % n1 == 0:
			count += 1
	r = 2 ** count - 1
	print(r)


def freq(arr):
	d = {}
	for i in arr:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	return d
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr = [i % k for i in arr]
	f = freq(arr)
	if 0 in f:
		print(2 ** f[0] - 1)
	else:
		print(0)


tests = int(input())
for i in range(tests):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	count = 0
	for j in arr:
		if j % m == 0:
			count += 1
	print(2 ** count - 1)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	c = 0
	for i in arr:
		if i % m == 0:
			c += 1
	print(2 ** c - 1)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [int(x) for x in input().split()]
	c = 0
	for i in a:
		if i % m == 0:
			c += 1
	print(2 ** c - 1)


import sys
import bisect
max_size = sys.maxsize
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	c = 0
	for i in range(n):
		if a[i] % m == 0:
			c += 1
	ans = 2 ** c - 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(j) for j in input().split()]
	cnt = 0
	for i in range(n):
		if a[i] % k == 0:
			cnt += 1
	print(2 ** cnt - 1)


t = int(input())
for _ in range(0, t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	count = 0
	for i in a:
		if i % k == 0:
			count = count + 1
	print(2 ** count - 1)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	lis = list(map(int, input().split()))
	cont = 0
	total = 0
	for i in lis:
		if i % m == 0:
			cont += 1
	total = (1 << cont) - 1
	print(total)


for i in range(int(input())):
	(N, M) = map(int, input().split())
	Array = list(map(int, input().split()))
	DivisibleArray = [i for i in Array if i % M == 0]
	print(2 ** len(DivisibleArray) - 1)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split(' '))
	l = list(map(int, input().split(' ')))
	c = 0
	for j in l:
		if j % m == 0:
			c = c + 1
	print(2 ** c - 1)


case = int(input())
for i in range(case):
	(n, m) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	ans = 1
	for val in arr:
		if val % m == 0:
			ans *= 2
	ans = ans - 1
	print(ans)


import math
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	arr = list(map(int, input().split()))
	count = 0
	for ele in arr:
		if ele % M == 0:
			count += 1
	ans = 2 ** count - 1
	print(ans)


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	listx = list(map(int, input().split()))
	count = 0
	for i in listx:
		if i % M == 0:
			count += 1
	print(2 ** count - 1)


T = int(input())
for tj in range(T):
	(N, M) = map(int, input().split())
	integers = list(map(int, input().split()))
	count = 0
	for i in range(N):
		if integers[i] % M == 0:
			count += 1
	print(2 ** count - 1)


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	c = 0
	for i in l:
		if i % m == 0:
			c += 1
	print(2 ** c - 1)


import numpy as np
t = int(input())
for i in range(0, t):
	c = list(map(int, input().split()))
	d = np.array(c)
	n = d[0]
	m = d[1]
	b = list(map(int, input().split()))
	a = np.array(b)
	k = 0
	for j in range(0, n):
		if a[j] % m == 0:
			k = k + 1
	if k == 0:
		print(0)
	elif k == 1:
		print(1)
	else:
		p = 2 ** k
		l = p - 1
		print(l)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	s = 2 ** sum([1 for j in l if j % k == 0]) - 1
	print(s)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	print(2 ** sum([1 for i in l if i % b == 0]) - 1)


try:
	T = int(input())
	for _ in range(T):
		(n, m) = map(int, input().split())
		a = list(map(int, input().split()))
		sm = 0
		for i in a:
			if i % m == 0:
				sm = sm + 1
		print(2 ** sm - 1)
except EOFError:
	pass


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	x = list(map(int, input().split()))
	xd = 0
	for i in range(n):
		if x[i] % m == 0:
			xd += 1
	print(2 ** xd - 1)


try:
	for i in range(int(input())):
		(n, m) = map(int, input().split())
		a = list(map(int, input().split()))
		c = 0
		for i in a:
			if i % m == 0:
				c += 1
		print(2 ** c - 1)
except:
	pass


tot = int(input())
for i in range(tot):
	(n, m) = map(int, input().split())
	b = list(map(int, input().split()))
	d = 0
	for i in b:
		if i % m == 0:
			d = d + 1
	print(2 ** d - 1)


t = int(input())
for I in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	c = 0
	for x in a:
		if x % m == 0:
			c += 1
	print(2 ** c - 1)


for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	cnt = sum([1 for x in arr if x % m == 0])
	print((1 << cnt) - 1)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	T = 0
	for i in range(N):
		if A[i] % K == 0:
			T += 1
	print(2 ** T - 1)


T1 = int(input())
for i in range(T1):
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = 0
	for j in range(a[0]):
		if b[j] % a[1] == 0:
			c = c + 1
	s = 2 ** c - 1
	print(s)


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	k = 0
	for i in l:
		if i % b == 0:
			k = k + 1
	print(2 ** k - 1)


t = int(input())
for j in range(t):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	count = 0
	for i in range(len(l)):
		if l[i] % b == 0:
			count = count + 1
	print(2 ** count - 1)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = list(map(int, input().split()))
	count = 0
	for i in s:
		if i % m == 0:
			count += 1
	print(2 ** count - 1)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	s = 0
	for j in range(n):
		if a[j] % m == 0:
			s += 1
	print(2 ** s - 1)


test_case = int(input())
for i in range(test_case):
	(size, num) = map(int, input().split())
	elements = list(map(int, input().split()))
	count = 0
	for j in elements:
		if j % num == 0:
			count += 1
	print(2 ** count - 1)