// Arup Guha
// 7/10/2014
// Solution to SI@UCF Week #1 Algorithms Contest Problem: Balance

import java.util.*;

public class balance {

    public static void main(String[] args) {

        Scanner stdin = new Scanner(System.in);
        int numCases = stdin.nextInt();

        // Go through each case.
        for (int loop=0; loop<numCases; loop++) {

            // Read in problem parameters.
            int n = stdin.nextInt();
            int[] weights = new int[n];
            for (int i=0; i<n; i++)
                weights[i] = stdin.nextInt();
            int target = stdin.nextInt();

            // Output result.
            System.out.println(solve(weights, target, 0));
        }
    }

    public static boolean solve(int[] weights, int target, int k) {

        // No more elements, must balance now.
        if (k == weights.length) return target == 0;

        // Three choices for each weight: don't use, left or right!
        return solve(weights, target, k+1) ||
               solve(weights, target-weights[k], k+1) ||
               solve(weights, target+weights[k], k+1);
    }
}