题目描述

小晨 想从 $n$ 个不同的数中选取一些数，使这些数的和为质数，请问 小晨 有多少种选择方法？

（如果两种方案选出来的数相同，就认为是同一种方案）

输入格式

输入第一行为一个整数 $n$，表示有 $n$ 个数。

接下来一行为空格隔开的 $n$ 个正整数，表示这 $n$ 个数。

输出格式

输出一行，为一个整数，即有多少种选择方案可以选一组数使得和为质数。

样例

3
1 2 3

4

5
1 2 3 4 5

12

样例 1 说明

有 $2、3、1+2=3、2+3=5$，$4$ 种方案

数据范围

对于 $60\%$ 的数据：$1\le n\le 3$；

对于 $100\%$ 的数据：$1\le n \le 20，1\le 每个数 \le 5\times 10^4$

提示

利用二进制进行枚举