题目描述

黑板上写着 $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$，您可以执行该操作两次。