問題文

黒板に $N$ 種類の整数が書かれています。 $i$ 種類目の整数は $A_i$ で、書かれている個数は $B_i$ 個です。

あなたは次の操作を可能な限り繰り返すことができます。

• 黒板に書かれている $2$ 個の整数 $x,y$ であって、$x+y$ が素数であるものを選ぶ。 選んだ $2$ 個の整数を黒板から消す。

操作を最大で何回行えるか求めてください。

制約

• $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$ は $4$ 個、 $3$ は $3$ 個あるので、操作を $3$ 回行うことができます。

入力例 2

1
1 4

出力例 2

2

$1+ 1 = 2$ であり、$2$ は素数なので、$1$ と $1$ を選んで消す操作が行えます。$1$ は $4$ 個あるので、操作を $2$ 回行うことができます。