Given a set A composed of non-negative integers, find if it has a subset with sum equal to a given target.

Example

A: [3, 0, 4, 9, 5]
target: 17
Result: True
Explanation: The subset [3, 9, 5] has a sum of 17

Testing

Input Format

The first line contains an integer ‘T’ denoting the number of test cases.
For each test case, the input has two lines:

• An integer ‘n’ denoting the length of the array A.
• n space-separated integers denoting the elements of the array A.

Output Format

For each test case, the output contains a line with one integer denoting if any subset has sum target - 1 if true, 0 if false.

Sample Input

4
5 17
3 0 4 9 5
5 20
3 0 4 9 5
5 16
2 2 5 4 8
1 2
1

Expected Output

1
0
1
0

Constraints

1 <= T <= 10
1 <= n <= 100
1 <= target <= 10000
0 <= Ai <= 10000