Description

After studying the Nim game and its variants, Orez discovered a brand-new stone-taking game, defined as follows:

There are $n$ piles of stones arranged in a row. Two players take turns. On each turn, a player may take any positive number of stones from either the leftmost pile or the rightmost pile; the entire pile may be taken, but taking zero stones is not allowed. The player who cannot move loses.

Orez asks: given any initial position, does there exist a winning strategy for the first player?

Input Format

The first line contains an integer $T$, the number of test cases.
For each test case:

• The first line contains an integer $n$, the number of piles.
• The second line contains $n$ integers $a_1, a_2, \ldots, a_n$, where $a_i$ is the number of stones in the $i$-th pile.

Output Format

For each test case, output a single integer $0$ or $1$. Here, $1$ means there exists a winning strategy for the first player, and $0$ means there is not.

1
4
3 1 9 4

0

Hint

• For $30\%$ of the testdata, $n \le 5$, $a_i \le 10^5$.
• For $100\%$ of the testdata, $1 \le T \le 10$, $1 \le n \le 1000$, $1 \le a_i \le 10^9$.

Translated by ChatGPT 5