当前没有测试数据。

G - 消除素数对

给定黑板上写有 $N$ 个不同值的整数。第 $i$ 个值是 $A_i$，出现了 $B_i$ 次。

你可以多次进行以下操作：

• 选择黑板上的两个整数 $x$ 和 $y$，使得 $x + y$ 是一个素数。然后擦掉这两个整数。

找出最大的操作次数。

约束条件

• $1 \leq N \leq 100$
• $1 \leq A_i \leq 10^7$
• $1 \leq B_i \leq 10^9$
• 所有的 $A_i$ 是不同的整数
• 输入中的所有值都是整数

输入 输入的格式如下： $N$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$

输出 输出答案。

样例输入1

3
3 3
2 4
6 2

样例输出1

3

我们有 $2 + 3 = 5$，而 $5$ 是一个素数，所以你可以选择擦去 $2$ 和 $3$，但没有其他的选择。因为有四个 $2$ 和三个 $3$，你最多可以进行三次操作。

样例输入2

1
1 4

样例输出2

2

我们有 $1 + 1 = 2$，而 $2$ 是一个素数，所以你可以选择擦去两个 $1$。因为有四个 $1$，你最多可以进行两次操作。