Problem Description

Alice and Bob are playing a game with an XOR sequence. At the beginning, Alice and Bob each have an integer $a$ and $b$ with initial value $0$, and they share a given sequence $X_{1}, X_{2}, \cdots, X_{n}$ of length $n$.

Alice and Bob take turns to make moves, with Alice moving first. In each move, one of the following two options can be chosen:

Option 1: Choose an $X_{i}$ from the sequence and XOR it to Alice's number, i.e., change $a$ to $a \oplus X_{i}$. (Here $\oplus$ denotes bitwise XOR.)

Option 2: Choose an $X_{i}$ from the sequence and XOR it to Bob's number, i.e., change $b$ to $b \oplus X_{i}$.

Each number $X_{i}$ can only be used once. When all $X_{i}$ have been used (after $n$ rounds), the game ends. At the end of the game, the player with the larger number wins. If both numbers are equal, the game is a draw.

Now assume both players are smart enough and both use optimal strategies. Determine who will win.

Input Format

Each test file contains multiple queries. The queries are independent.

The first line contains an integer $T$, which is the number of queries.

The next $T$ lines each contain one query. In the $i$-th line, the first integer $n_{i}$ is the length of the sequence, followed by $n_{i}$ integers $X_{1}, X_{2}, \cdots, X_{n_{i}}$, which are the numbers in the sequence.

Output Format

Output $T$ lines, each corresponding to the answer for one query.

Each line contains an integer $1$, $0$, or $-1$, meaning that Alice wins, the game is a draw, or Alice loses, respectively.

4
1 1
1 0
2 2 1
7 992438 1006399 781139 985280 4729 872779 563580

1
0
1
1

Hint

For all test cases, $1 \leq T \leq 2\times 10^5$, $1 \leq \sum\limits_{i=1}^{T} n_{i} \leq 2\times10^5$, $0 \leq X_{i}<2^{20}$.

Lanqiao Cup 2021, Round 1, Provincial Contest, Group A, Problem G.

Translated by ChatGPT 5