Description

数学王国的质数部长是质数的狂热追随者，因此他特别设立了一个部门来解决与质数相关的问题。这个部门的负责人罗伯特先生最近收到了他的朋友欧拉的一封信。

这封信中包含了一个关于质数的谜题。欧拉认为序列 \(a_1, a_2, ..., a_n\) 是美丽的当且仅当所有元素都是正整数，并且任意两个相邻元素的和是一个质数。

形式化地说，\(\forall i\in [1, n] \cap \mathbb{N}, a_i \in \mathbb{N}^+,\forall i\in [1, n) \cap \mathbb{N}, (a_i+a_{i+1}) \in \mathbb{P}\)，其中 \(\mathbb{P}\) 表示包含所有质数的集合。

有时，欧拉信中给定的序列并不美丽。罗伯特先生希望通过修改最少数量的序列元素使其变得美丽。

罗伯特先生最近很忙，所以他想请你帮忙计算使序列变得美丽的最小修改数量。

Input

第一行包含一个整数 \(n\ (2\le n \le 10^5)\)。

第二行包含 \(n\) 个正整数，表示 \(a_1, a_2,...,a_n\ (1\le a_i\le 10^5)\)。

Output

输出一个整数，表示使序列变得美丽的最小更新元素数量。

6
1 5 1 4 4 1
##CASE##
9
30 6 7 12 15 8 20 17 14

2
##CASE##
4

Hint

对于第一个测试，更新后的序列可以是 “1 2 1 1 4 1”。