[ZJOI2009]取石子游戏

在研究过 Nim 游戏及其各种变种后，Orez 又发现了一种新的取石子游戏。

有 $n$ 堆石子排成一列。两名玩家轮流操作，每次可以从最左端或最右端的一堆石子中取出若干颗石子。玩家可以将所选石子堆全部取完，但每次操作至少要取出一颗石子。无法进行操作的玩家失败。

对于任意给定的初始局面，请判断先手是否存在必胜策略。

输入格式

第一行包含一个整数 $T$，表示测试数据的组数。

对于每组测试数据：

• 第一行包含一个整数 $n$，表示石子堆的数量；
• 第二行包含 $n$ 个整数 $a_i$，依次表示每堆石子的数量。

输出格式

对于每组测试数据，输出一个整数 $0$ 或 $1$。

若先手存在必胜策略，则输出 $1$；否则输出 $0$。

样例输入

1
4
3 1 9 4

样例输出

0

数据范围

• 对于 $30\%$ 的数据，$n\le 5$，$a_i\le 10^5$；
• 对于 $100\%$ 的数据，$T\le 10$，$n\le 1000$，$a_i\le 10^9$。

来源与许可

本题为 ZJOI 2009 试题「取石子游戏」，题面与测试数据整理自 BZOJ。

样例 1

输入

1
4
3 1 9 4

输出

0