A. 素数伴侣

若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如 $2$ 和 $5$、$6$ 和 $13$，它们能应用于通信加密。

现在密码学会请你设计一个程序，从已有的 $n$ 个正整数中挑选出若干对组成“素数伴侣”，挑选方案多种多样，例如有 $4$ 个正整数：$2,5,6,13$，如果将 $5$ 和 $6$ 分为一组中只能得到一组“素数伴侣”，而将 $2$ 和 $5$、$6$ 和 $13$ 编组将得到两组“素数伴侣”，能组成“素数伴侣”最多的方案称为“最佳方案”。

显然，密码学会希望你寻找出“最佳方案”。请你帮助他们。

本题为多组输入样例。

第一行一个正整数 $T(1\leq T\leq 10)$ 表示数据组数。

对于每组数据共输入两行，第一行一个正整数 $n(2\leq n\leq 1000)$ 代表待配对的正整数个数；第二行 $n$ 个用空格分隔的正整数 $a_i(2\leq a_i\leq 30000)$ 代表待配对的正整数。

对于每组数据输出一行一个正整数，代表每组数据的最佳配对方案下的配对数。

输入样例

2
4
2 5 6 13
2
3 6

输出样例

2
0