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

There are $n$ piles of stones arranged in a row. The game is played by two players who take turns. In each turn, a player can take any number of stones from either the leftmost or the rightmost pile. A player may choose to remove the entire pile, but they must take at least one stone. The player who cannot make a move loses.

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

Input

The first line contains an integer $T$, representing the number of test cases. For each test case, the first line contains an integer $n$, representing the number of piles of stones; the second line contains $n$ integers $a_i$, representing the number of stones in each pile in order.

Output

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

Examples

Input 1

1
4
3 1 9 4

Output 1

0

Constraints

For 30% of the data: $n \le 5$, $a_i \le 10^5$.

For 100% of the data: $T \le 10$, $n \le 1000$, the number of stones in each pile $\le 10^9$.