Prime Swaps

2000ms

262144K

Description:

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 5n operations.

Input:

The first line contains integer n (1 ≤ n ≤ 10⁵). 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 ≤ 5n) — 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.

Sample Input:

3
3 2 1

Sample Output:

1
1 3

Sample Input:

2
1 2

Sample Output:

Sample Input:

4
4 2 3 1

Sample Output:

Informação

Provedor Codeforces

Código CF432C