Mystery of Prime
Description
The prime minister of the Mathematical Kingdom is a crazy follower of prime numbers, therefore he especially set up a department to solve problems related to prime numbers. The head of this department, Mr.Robert, recently received a letter from his friend Euler.
The letter contains a mystery of prime. There is a sequence $a_1, a_2, ..., a_n$. Euler considers a sequence beautiful if and only if all elements are $\textbf{positive}$ integers and the sum of any two adjacent elements is a prime.
Formally,$\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},$ where $\mathbb{P}$ represents the set containing all primes.
Sometimes, the given sequence is not beautiful. Mr.Robert would like to make the least effort to make it beautiful, that is to modify the elements of the sequence and minimize the number of updated elements.
Mr.Robert is busy these days, so he asked you to report the minimum number of updated elements to make the sequence beautiful.
The first line contains an integer $n\ (2\le n \le 10^5)$.
The second line contains $n$ positive integers, representing $a_1, a_2,...,a_n\ (1\le a_i\le 10^5)$.
Print a single integer representing the minimum number of updated elements to make the sequence beautiful.
Input
The first line contains an integer $n\ (2\le n \le 10^5)$.
The second line contains $n$ positive integers, representing $a_1, a_2,...,a_n\ (1\le a_i\le 10^5)$.
Output
Print a single integer representing the minimum number of updated elements to make the sequence beautiful.
6
1 5 1 4 4 1
9
30 6 7 12 15 8 20 17 14
2
4
Note
For the first test, the updated sequence may be "1 2 1 1 4 1".