小蓝和小乔正在玩一个游戏：对给定的 n 堆石子，每次可以选一堆石子分成相等的质数份或直接消去。双方轮流操作，轮到某玩家操作时如果没有任何石子则这个玩家失败。
小蓝先操作（先手），小乔后操作。
请问小蓝是否存在必胜策略，即是不是存在一种策略，使得不论小乔如何操作，小蓝总有办法获得胜利。
输入包含多组独立的询问。
输入的第一行包含一个整数 T 表示询问的组数。
接下来依次描述每一组询问。
每组询问的第一行包含一个整数 ni ，表示石子的堆数。
第二行包含 n 个正整数，相邻两个整数之间用一个空格分隔，依次表示每堆石子的个数。
输出 T 行，每行包含一个整数 0 或 1，表示对应询问的答案。如果小蓝存在必胜策略，输出 1，否则输出 0 。
2 2 2 3 5 4 15 1 9 6
1 1
对于 20% 的评测用例，T = 1 ，ni ≤ 10 ，每堆石子数量不超过 1000；
对于 50% 的评测用例，∑ni ≤10000；
对于所有评测用例，1 ≤T≤105 ，1≤ ni ，∑ ni ≤ 105 ，每堆石子数量不超过 106 。