该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

小蓝和小乔正在玩一个游戏: 对给定的 $n$ 堆石子, 每次可以选一堆石子分成相等的质数份或直接消去。双方轮流操作, 轮到某玩家操作时如果没有任何石子则这个玩家失败。

小蓝先操作 (先手), 小乔后操作。

请问小蓝是否存在必胜策略, 即是不是存在一种策略, 使得不论小乔如何操作, 小蓝总有办法获得胜利。

输入格式

输入包含多组独立的询问。

输入的第一行包含一个整数 $T$ 表示询问的组数。

接下来依次描述每一组询问。

每组询问的第一行包含一个整数 $n_i$, 表示石子的堆数。

第二行包含 $n$ 个正整数, 相邻两个整数之间用一个空格分隔, 依次表示每堆石子的个数。

输出格式

输出 $T$ 行, 每行包含一个整数 0 或 1 , 表示对应询问的答案。如果小蓝存在必胜策略, 输出 1 , 否则输出 0 。

2
2
2 3
5
4 15 1 9 6

1
1

评测用例规模与约定

对于 20% 的评测用例, $T=1, n_i \leq 10$, 每堆石子数量不超过 1000 ;

对于 50% 的评测用例, $\sum n_i \leq 10000$;

对于所有评测用例, $1 \leq T \leq 10^5, 1 \leq n_i, \sum n_i \leq 10^5$, 每堆石子数量不超过 $10^6$。