public class Main19 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int group = Integer.parseInt(br.readLine());
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < group; i++) {
            int num = Integer.parseInt(br.readLine());
            String[] letters = br.readLine().split("\\ ");
            int[] nums = new int[num];
            for (int j = 0; j < num; j++) {
                nums[j] = Integer.parseInt(letters[j]);
            }
            
            Arrays.sort(nums);
            findMinValue(nums, nums.length - 1, 0);
            int result = 0;
            if (minIndex != Integer.MAX_VALUE && minIndex >= 0) {
                result = getMinRes(nums, minIndex);
            }
            minIndex = Integer.MAX_VALUE;
            res.add(result);
        }
        for (int i = 0; i < res.size(); i++) {
            System.out.println(res.get(i));
        }
    }

    private static int minIndex = Integer.MAX_VALUE;

    private static void findMinValue(int[] nums, int index, int cur) {
        if (index < 0) {
            return;
        }
        if (cur + nums[index] == 0 || cur - nums[index] == 0) {
            minIndex = Math.min(minIndex, index - 1);
        }
        findMinValue(nums, index - 1, cur + nums[index]);
        findMinValue(nums, index - 1, cur - nums[index]);
    }

    private static int getMinRes(int[] nums, int index) {
        int result = 0;
        for (int i = index; i >= 0; i--) {
            result += nums[i];
        }
        return result;
    }
}