## GUPTA MECHANICAL

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

## [Solution] Max Shift After XOR CodeChef Solution | CodeChef Problem Solution 2022

You are given an array $A$, consisting of $N$ integers.

Consider the following definitions:

• Prefix xor array of an array $A$ is defined as the array $B$ such that ${B}_{i}={A}_{1}\oplus \dots \oplus {A}_{i}$, where $\oplus$ denotes bitwise XOR operation.
In other words, $B=\left[{A}_{1},{A}_{1}\oplus {A}_{2},\dots ,{A}_{1}\oplus {A}_{2}\dots \oplus {A}_{N}\right]$
• The value of an array $A$ is the number of distinct values in array $B$. For example, for array $A=\left[1,2,3,0\right]$, we have $B=\left[1,3,0,0\right]$. The array $B$ has $3$ distinct values, thus, the value of array $A$ is $3$.
• One right shift on the array $A$ is a transformation that changes the array $A=\left[{A}_{1},{A}_{2}\dots ,{A}_{N}\right]$ to ${A}^{{}^{\prime }}=\left[{A}_{N},{A}_{1},\dots ,{A}_{N-1}\right]$.

Calculate the maximum value of the array $A$ you can get, by performing any (possibly zero) number of right shifts on the array $A$.

### Input Format

• The first line of input contains $T$ $-$ the number of test cases you need to solve.
• The first line of each test case contains one integer $N$ $-$ the size of the array.
• The second line of each test case contains $N$ space-separated integers ${A}_{1},\dots ,{A}_{N}$ $-$ the

•  elements of the array $A$.

### Output Format

For each test case, output on a new line the maximum value of an array $A$ you can achieve after performing any (possibly zero) number of right shifts on the array.

### Constraints

• $1\le T\le {10}^{5}$
• $2\le N\le 2\cdot {10}^{5}$
• $0\le {A}_{i}\le {2}^{60}-1$
• Sum of $N$ over all test cases doesn't exceed $2\cdot {10}^{5}$.