Given an array of integers A and a target value target.

Find whether there exists a subset in the array A where their sum is equal to target.

Example:

A: [1, 3, 4, 9, 2]

target: 13

Result: Subset exists.

Subset [1, 3, 9] has a sum equal to 13.

Testing

Input Format

The first line contains an integer ‘T’, denoting the number of test cases.

For each test case the input has three lines:

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

Output Format

For each test case, the output has a line with 1 or 0 depending on whether the subset exists or not respectively.

Sample Input

2
5
1 1 2 3 4
5
5
1 3 1 3 4
20

Expected Output

1
0

Constraint

1 <= T <= 100
1 <= n <= 16
1 <= Ai <= 500
1 <= target <= 500