You have an array $*a*[1], *a*[2], ..., *a*[*n*]$, containing distinct integers from $1$ to $*n*$. Your task is to sort this array in increasing order with the following operation (you may need to apply it multiple times):

• choose two indexes, $*i*$ and $*j*$ ($1 ≤ *i* < *j* ≤ *n*$; $(*j* - *i* + 1)$ is a prime number);
• swap the elements on positions $*i*$ and $*j*$; in other words, you are allowed to apply the following sequence of assignments: $*tmp* = *a*[*i*], *a*[*i*] = *a*[*j*], *a*[*j*] = *tmp*$ ($*tmp*$ is a temporary variable).

You do not need to minimize the number of used operations. However, you need to make sure that there are at most $5*n*$ operations.

Input

The first line contains integer $*n*$ $(1 ≤ *n* ≤ 10^{5})$. The next line contains $*n*$ distinct integers $*a*[1], *a*[2], ..., *a*[*n*]$ $(1 ≤ *a*[*i*] ≤ *n*)$.

Output

In the first line, print integer $*k*$ $(0 ≤ *k* ≤ 5*n*)$ — the number of used operations. Next, print the operations. Each operation must be printed as "$*i*$ $*j*$" ($1 ≤ *i* < *j* ≤ *n*$; $(*j* - *i* + 1)$ is a prime).

If there are multiple answers, you can print any of them.