The Equation

Interview

Time limit15sMemory limit1024 MB

Summary

Given N integers and a limit M, find the largest k such that the sum of each A_i XOR k is at most M, or report -1 if no k works.

Level: Medium5 of 10
Topics: Bit manipulation, Greedy
Solved: No attempts yet

Problem

The laws of the universe can be represented by an array of N non-negative integers. The i-th of these integers is A_i.

The universe is good if there is a non-negative integer k such that the following equation is satisfied: $(A_1 \oplus k) + (A_2 \oplus k) + \cdots + (A_N \oplus k) \le M$ , where $\oplus$ denotes the bitwise exclusive or.

What is the largest value of k for which the universe is good?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the two integers N and M, the number of integers in A and the limit on the equation, respectively.

The second line contains N integers, the i-th of which is A_i, the i-th integer in the array.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the largest value of k for which the universe is good, or -1 if there is no such k.

Constraints

1 ≤ T ≤ 100.
1 ≤ N ≤ 1000.

Hint

In sample case #1, the array contains N = 3 integers and M = 27. The largest possible value of k that gives a good universe is 12 ((8 xor 12) + (2 xor 12) + (4 xor 12) = 26).

In sample case #2, the array contains N = 4 integers and M = 45. The largest possible value of k that gives a good universe is 14 ((30 xor 14) + (0 xor 14) + (4 xor 14) + (11 xor 14) = 45).

In sample case #3, the array contains N = 1 integer and M = 0. The largest possible value of k that gives a good universe is 100 (100 xor 100 = 0).

In sample case #4, there is no value of k that gives a good universe, so the answer is -1.

Examples1

Example 1

Input

4
3 27
8 2 4
4 45
30 0 4 11
1 0
100
6 2
5 5 1 5 1 0

Expected output

Case #1: 12
Case #2: 14
Case #3: 100
Case #4: -1