There are infinitely many cards, numbered 1, 2, 3, ... Initially, Cards x_1, x_2, ..., x_N are face up, and the others are face down.

Snuke can perform the following operation repeatedly:

• Select a prime p greater than or equal to 3. Then, select p consecutive cards and flip all of them.

Snuke's objective is to have all the cards face down. Find the minimum number of operations required to achieve the objective.

Constraints

• 1 ≤ N ≤ 100
• 1 ≤ x_1 < x_2 < ... < x_N ≤ 10^7

Input

Input is given from Standard Input in the following format:

N
x_1 x_2 ... x_N

Output

Print the minimum number of operations required to achieve the objective.

Examples

Input

2
4 5

Output

2

Input

9
1 2 3 4 5 6 7 8 9

Output

3

Input

2
1 10000000

Output

4

见题面

见题面