An established group of scientists are working on finding solution to NP hard problems. They claim Subset Sum  as an NP-hard problem. The problem is to determine whether there exists a subset of a given set S whose sum is a given number K.  
You are a computer engineer and you claim to solve this problem given that all numbers in the set are non-negative. Given a set S of size N of non-negative integers, find whether there exists a subset whose sum is K.

Input
First line of input contains T, the number of test cases. T test cases follow. 
Each test case contains 2 lines. First line contains two integers N and K. Next line contains N space separated non-negative integers (each less than 100000).
0 < T < 1000
0 < N < 1000
0 < K < 1000

Output
Output T lines, one for each test case. Every line should be either 0 or 1 depending on whether such a subset exists or not.

Example

Input:
2
5 10
3 4 6 1 9
3 2
1 3 4

Output:
1
0
import sys

for __ in range(input()) :
    n , k = map(int,sys.stdin.readline().split())
    lists = map(int,sys.stdin.readline().split())
    dp = [0]*(k+1)
    dp[0]=1
    for i in lists :
        for j in range(k-i,-1,-1) :
            if dp[k] :
                break
            if dp[j] :
                dp[j+i] = 1
    print dp[k]