## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## Maximum OR Minimum CodeChef Solution | CodeChef Problem Solution 2022

Alice and Bob are ready to play a new game. Both the players take alternate turns. Alice starts first.

There are $N$ binary numbers written on a blackboard.

• Alice, in her turn, erases any $2$ numbers from the blackboard and writes the bitwise OR of those $2$ numbers on the blackboard.
• Bob, in his turn, erases any $2$ numbers from the blackboard and writes the bitwise AND of those $2$ numbers on the blackboard.

Note that, after each move, the count of numbers written on the blackboard reduces by $1$.

Both players play until a single number remains on the blackboard. Alice wants to maximise the remaining number while Bob wants to minimise the remaining number. Find the remaining number if both the players play optimally.

### Input Format

• First line will contain $T$, number of test cases. Then the test cases follow.
• First line of each test case contains of a single integer $N$ - the count of numbers written on the blackboard initially.
• Second line of each test case contains $N$ space-separated integers ${A}_{1},{A}_{2},\dots {A}_{N}$ - the numbers written on the blackboard.

### Output Format

For each test case, output in a single line, the remaining number, if both the players play optimally.

### Constraints

• $1\le T\le 1000$
• $2\le N\le {10}^{5}$
• $0\le {A}_{i}\le 1$
• Sum of $N$ over all test cases does not exceed $2\cdot {10}^{5}$.

### Sample Input 1

3
5
1 1 1 1 0
3
0 1 0
4
0 0 0 0


### Sample Output 1

1
0
0


### Explanation

Test case $1$: Alice starts first.

• In the first move, Alice erases $1$ and $0$ and writes $1|0=1$ on the blackboard. Thus, after this move, the numbers written are $\left\{1,1,1,1\right\}$.
• In the second move, Bob erases $1$ and $1$ and writes $1\mathrm{&}1=1$ on the blackboard. Thus, after this move, the numbers written are $\left\{1,1,1\right\}$.
• In the third move, Alice erases $1$ and $1$ and writes $1|1=1$ on the blackboard. Thus, after this move, the numbers written are $\left\{1,1\right\}$.
• In the fourth move, Bob erases $1$ and $1$ and writes $1\mathrm{&}1=1$ on the blackboard. Thus, after this move, the numbers written are $\left\{1\right\}$.

Thus, the remaining number is $1$.

Test case $2$: It does not matter which two numbers Alice chooses. After the first move, the numbers on the blackboard would be $\left\{1,0\right\}$. Thus, Bob erases these two numbers and writes $1\mathrm{&}0=0$.

Test case $3$: In all the moves, both players erase two $0s$ and write a single $0$. Thus, the remaining element is $0$.