6748 - 取石子游戏Ⅳ
时间限制 : 1 秒
内存限制 : 128 MB
在研究过Nim游戏及各种变种之后，Orea又发现了一种全新的取石子游戏，这个游戏是这样的：
有n堆石子，将这n堆石子摆成一排，游戏由两个人进行，两个人轮流操作，每次操作者都可以从最左或最右的一堆中取出若干颗石子，可以将那一堆全部取掉，但不能不取，不能操作的人就输了。
Orea问：对于任意给出的一个初始局面，是否存在先手必胜策略。
输入
第一行为一个整数T，表示有T组测试数据。
对于每组测试数据，第一行为一个整数n，表示有n堆石子;第二行为n个整数ai，依次表示每堆石子的数目
输出
对于每组测试数据仅输出一个整数0或1。其中1表示有先手必胜策略，0表示没有。
样例
输入
1 4 3 1 9 4
输出
0
提示
【数据规模】
对于30％的数据，n≤5，ai≤10的5次。
对于100％的数据，T≤10，n≤1000，每堆的石子数目≤10的9次。
来源
一本通提高