Description

I have a pen, I have an apple. Eh, Apple-Pen!
I have a pen, I have pineapple. En, Pineapple-Pen!
Apple-Pen, Pineapple-Pen. Eh, Pen-Pineapple-Apple-Pen!

Akn has recently become obsessed with a song, so he bought a bunch of apples to learn it. He discovered that as long as he sings the song while making the gesture of bumping two whole apples together, the two apples will fuse into one new big apple. However, the big apple can no longer fuse again because its internal cellular structure has changed. Akn also found that when two apples fuse, the mass of the resulting apple is the bitwise AND operation ($a \operatorname{and} b$). Recently, one of his classmates asked him for an apple to eat. Out of kindness, Akn plans to give his classmate the big apple formed by fusing the apples he used to learn PPAP, so that the classmate can also get into PPAP. Moreover, Akn wants the mass of the big apple to be as large as possible. What is the maximum mass of the big apple that Akn can give to his classmate?

Input Format

The first line contains an integer $t$, the number of test cases.

For each of the next $t$ test cases, the first line contains an integer $n$, the number of apples.

The second line contains $n$ integers $w_i$, where the $i$-th small apple weighs $w_i\ \text{kg}$.

Output Format

For each test case, output one line with a single integer, the maximum mass of the big apple. Note the format: Case #x: ans. There is a space between Case and #, and a space between : and ans.

3
4
1 3 5 7
10
32 54 21 52 14 25 92 75 14 27
21
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576

Case #1: 5 
Case #2: 72
Case #3: 0

Hint

Due to testdata package size limits, only part of the testdata is uploaded (points $1,2,3,4,5,6,7,8,10,11,12,13,16,19,20$).

Explanation for the first test set:

1(2)=1
3(2)=11
5(2)=101
7(2)=111

Choose $5$ and $7$ to fuse, and the final answer is $5$.

Constraints:

• For $10\%$ of the testdata, $n \le 5000, t \le 1$.
• For another $10\%$ of the testdata, $n \le 2000, t \le 6$.
• For another $20\%$ of the testdata, $a \le 2^{10}$.
• For another $5\%$ of the testdata, $n \le 10^5, a \le 2^{20}$, and the two largest numbers are equal.
• For another $20\%$ of the testdata, $n \le 10^4, a \le 2^{15}$.
• For another $15\%$ of the testdata, $n \le 10^5, a \le 2^{20}, t \le 6$.
• For another $15\%$ of the testdata, $n \le 10^5, a \le 2^{20}, t \le 12$.
• For $100\%$ of the testdata, $n \le 10^5, a \le 2^{20}, t \le 20$.

By: worcher

Translated by ChatGPT 5