Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Prime Swaps

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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.

Examples

Input

3

3 2 1

Output

1

1 3

Input

2

1 2

Output

0

Input

4

4 2 3 1

Output

3

2 4

1 2

2 4

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/31/2023 13:58:46 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|