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.

Difficulty: interview

Starter code:

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

# cook your dish here
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

# cook your dish here
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))

# cook your dish here
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))

# cook your dish here
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):
	# print(i,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))


# cook your dish here
def subset_sum(numbers, target, partial=[]):
    count=0
    s = sum(partial)

    # check if the partial sum is equals to target
    if s == target: 
        count+=1
        return 1
    if s >= target:
        return 0# if we reach the number why bother to continue

    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))



# cook your dish here
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

# cook your dish here
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

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

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 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] 
# cook your dish here
for _ in range ( int(input())):
    n=int(input())
    s=int(input())
    a=list(map(int,input().split()))
    print(help(a,s))