Since due to COVID 19, India has undergone a complete 21 day lockdown. So Amol was attending an online lecture where his professor asked him to solve a question. Amol was unable to solve the question so he asked you to solve the question and give him the correct answer. 

The question was asked a such that his professor gave him a number M and a list of integers of length N (i.e. A1, A2,..... AN) and you have to find out all the subsets that add up to M and the total number of subsets will be the final answer. 

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 a single integer N. 

• The second line of each test case contains a single integer M. 

• The third line contains N space-separated integers A1, A2,..... AN. 

Output: 
For each test case, print a single line containing one integer ― the no. of subsets that adds upto M.

Constraints: 
• 1≤T≤5

• 1≤N≤100 

• 10≤M≤100 

• 1≤Ai≤100

ExampleInput:

2

4

16

2 4 6 10 

4 

20 

2 8 12 10 

Output:

2

2

Explanation:
In the 1st example there are two subsets {2,4,10} and {6,10} that adds upto 16 so the output is 2.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
try:

	def countsubsetsum(S, arr, n):
		k = [[0 for i in range(S + 1)] for i in range(n + 1)]
		for i in range(n + 1):
			for j in range(S + 1):
				if j == 0:
					k[i][j] = 1
				elif i == 0:
					k[i][j] = 0
				elif arr[i - 1] <= j:
					k[i][j] = k[i - 1][j - arr[i - 1]] + k[i - 1][j]
				else:
					k[i][j] = k[i - 1][j]
		return k[n][S]
	for _ in range(int(input())):
		m = int(input())
		S = int(input())
		arr = [int(i) for i in input().split()]
		n = len(arr)
		print(countsubsetsum(S, arr, n))
except EOFError as e:
	pass


class Solution:

	def solve(self, A, target):
		A.sort()
		self.count = 0
		self.count_sixlets(A, 0, target)
		return self.count

	def count_sixlets(self, A, _sum, target):
		if _sum == target:
			self.count += 1
			return
		for i in range(0, len(A)):
			if _sum + A[i] > target:
				break
			self.count_sixlets(A[i + 1:], _sum + A[i], target)
t = int(input())
obj = Solution()
while t > 0:
	n = int(input())
	_sum = int(input())
	_list = list(map(int, input().split()))
	obj.solve(_list, _sum)
	print(obj.count)
	t -= 1


def countsubsetsum(S, arr, n):
	k = [[0 for i in range(S + 1)] for i in range(n + 1)]
	for i in range(n + 1):
		for j in range(S + 1):
			if j == 0:
				k[i][j] = 1
			elif i == 0:
				k[i][j] = 0
			elif arr[i - 1] <= j:
				k[i][j] = k[i - 1][j - arr[i - 1]] + k[i - 1][j]
			else:
				k[i][j] = k[i - 1][j]
	return k[n][S]
for _ in range(int(input())):
	m = int(input())
	S = int(input())
	arr = [int(i) for i in input().split()]
	n = len(arr)
	print(countsubsetsum(S, arr, n))


def solve(l, i, n, m):
	if m == 0:
		return 1
	elif i >= n:
		return 0
	elif m < 0:
		return 0
	else:
		return solve(l, i + 1, n, m - l[i]) + solve(l, i + 1, n, m)
T = int(input())
for _ in range(T):
	N = int(input())
	M = int(input())
	l = list(map(int, input().split()))
	print(solve(l, 0, len(l), M))


def subset_sum(numbers, target, partial=[]):
	count = 0
	s = sum(partial)
	if s == target:
		count += 1
		return 1
	if s >= target:
		return 0
	for i in range(len(numbers)):
		n = numbers[i]
		remaining = numbers[i + 1:]
		count += subset_sum(remaining, target, partial + [n])
	return count
t = int(input())
for i in range(t):
	input()
	n = int(input())
	s = list(map(int, input().split()))
	print(subset_sum(s, n))


try:

	def um(a, r, x):
		z = [[0 for i in range(a + 1)] for i in range(x + 1)]
		for i in range(x + 1):
			for j in range(a + 1):
				if j == 0:
					z[i][j] = 1
				elif i == 0:
					z[i][j] = 0
				elif r[i - 1] <= j:
					z[i][j] = z[i - 1][j - r[i - 1]] + z[i - 1][j]
				else:
					z[i][j] = z[i - 1][j]
		return z[x][a]
	for _ in range(int(input())):
		b = int(input())
		a = int(input())
		r = [int(i) for i in input().split()]
		x = len(r)
		print(um(a, r, x))
except EOFError as y:
	pass


try:

	def help(a, s):
		dp = [[0 for i in range(len(a))] for j in range(0, s + 1)]
		for i in range(len(a)):
			dp[0][i] = 1
		for i in range(1, s + 1):
			if i == a[0]:
				dp[i][0] = 1
		for i in range(1, s + 1):
			for j in range(1, len(a)):
				if a[j] <= i:
					dp[i][j] = dp[i][j - 1] + dp[i - a[j]][j - 1]
				else:
					dp[i][j] = dp[i][j - 1]
		return dp[s][len(a) - 1]
	test = int(input())
	for i in range(test):
		no1 = int(input())
		s = int(input())
		a = []
		a = [int(x) for x in input().split()]
		print(help(a, s))
except EOFError:
	pass


def isSubsetSum(set, n, sum):
	if sum == 0:
		return 1
	if n == 0 and sum != 0:
		return 0
	if set[n - 1] > sum:
		return isSubsetSum(set, n - 1, sum)
	return isSubsetSum(set, n - 1, sum) + isSubsetSum(set, n - 1, sum - set[n - 1])

def __starting_point():
	t = int(input())
	while t > 0:
		n = int(input())
		m = int(input())
		arr = list(map(int, input().split()))
		print(isSubsetSum(arr, n, m))
		t -= 1
__starting_point()


def help(a, s):
	dp = [[0 for i in range(len(a))] for j in range(0, s + 1)]
	for i in range(len(a)):
		dp[0][i] = 1
	for i in range(1, s + 1):
		if i == a[0]:
			dp[i][0] = 1
	for i in range(1, s + 1):
		for j in range(1, len(a)):
			if a[j] <= i:
				dp[i][j] = dp[i][j - 1] + dp[i - a[j]][j - 1]
			else:
				dp[i][j] = dp[i][j - 1]
	return dp[s][len(a) - 1]
for _ in range(int(input())):
	n = int(input())
	s = int(input())
	a = list(map(int, input().split()))
	print(help(a, s))