Description

Original Source: ZJOI 2009

After studying the Nim game and its various variants, Orez discovered a brand-new stone-picking game. The rules are as follows:

There are $n$ piles of stones arranged in a row. Two players take turns to play. On each turn, the player can remove any number of stones from either the leftmost or the rightmost pile. The player can take all the stones from the chosen pile but must take at least one stone. The player who cannot make a move loses.

Orez asks: Given any initial configuration, does the first player have a winning strategy?

Input Format

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

For each test case, the first line contains an integer $n$, representing the number of piles. The second line contains $n$ integers $a_i$, denoting the number of stones in each pile from left to right.

Output Format

For each test case, output a single integer $0$ or $1$. Here, $1$ indicates that the first player has a winning strategy, while $0$ means they do not.

Sample 1

1
4
3 1 9 4

0

Data Range and Hints

For $30\%$ of the data, $n\le 5$ and $a_i\le 10^5$;
For all data, $1\le T\le 10$, $1\le n\le 1000$, and the number of stones in each pile is less than or equal to $10^9$.