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 ≤ 105). 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.

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
import java.io.*;
import java.util.*;
import static java.lang.Math.*;

/** 432/C Prime Swap -- godmar@gmail.com 
 * Approach: build all Goldbach decompositions.
 * Then swap any two elements with at most 5 swaps.
 */
public class SortSimpler {
    static boolean [] isPrime;
    static int [][] goldbachDecom;

    public static void main(String []av) {
        Scanner s  = new Scanner();
        int n = s.nextInt();

        isPrime = sieve(n+10);
        goldbachDecom = findGoldbach3(isPrime);

        int [] a = new int[n];
        for (int i = 0; i < n; i++)
            a[s.nextInt() - 1] = i;

        int nOps = 0;
        StringBuilder ops = new StringBuilder();

        for (int i = 0; i < a.length; i++) {
            if (a[i] == -1)
                continue;

            // follow cycle starting in i
            int j = i;
            while (a[j] != i) {
                int oldj = j;
                j = a[j];
                nOps += doSwap(ops, oldj, j);
                a[oldj] = -1;
            }
            a[j] = -1;
        }

        System.out.println(nOps);
        System.out.print(ops.toString());

    }

    static int doSwap(StringBuilder os, int i, int j) {
        int w1 = min(i, j);
        int w2 = max(i, j);
        if (isPrime[1 + w2 - w1]) {
            outputSwap(os, w1, w2);
            return 1;
        } else {
            int [] p = goldbachDecom[3 + w2 - w1];

            int a = w1;
            int b = a + p[0] - 1;
            int c = b + p[1] - 1;
            int d = c + p[2] - 1;

            outputSwap(os, a, b);
            outputSwap(os, c, d);
            outputSwap(os, b, c);
            outputSwap(os, a, b);
            outputSwap(os, c, d);
            return 5;
        }
    }

    static void outputSwap(StringBuilder os, int i, int j) {
        os.append(Integer.toString(1 + min(i, j)));
        os.append(' ');
        os.append(Integer.toString(1 + max(i, j)));
        os.append('\n');
    }

    /**
     * Find decomposition into 3 primes for all n less than
     * isPrime.length.  All decompositions are of the form
     * 2, p, q for even numbers and 3, p, q for odd numbers.
     */
    static int [][] findGoldbach3(boolean [] isPrime) {
        int n = isPrime.length;
        int [][] r = new int[n+6][];
        r[2] = new int[] {2};
        r[3] = new int[] {3};
        r[4] = new int[] {2, 2};
        r[5] = new int[] {2, 3};

        int left = n - 6;
        for (int i = 2; i < n; i++) if (isPrime[i]) {
            for (int j = 2; j < n; j++) if (isPrime[j]) {
                if (left <= 0)
                    return r;

                if (i + j + 3 >= n)
                    break;

                if (r[i + j + 2] == null) {
                    left--;
                    r[i + j + 2] = new int[] {2, i, j};
                }

                if (r[i + j + 3] == null) {
                    left--;
                    r[i + j + 3] = new int[] {3, i, j};
                }
            }
        }
        return r;
    }

    /*
     * Implementation of the Sieve of Eratosthenes
     * 
     * Generates a boolean array where the value 'true'
     * indicates that index being a prime number.
     * 
     * Generates all primes up to and including N.
     */
    public static boolean[] sieve(int N)
    {

        boolean[] isPrime = new boolean[N + 1];

        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;

        // Iterate through all numbers up to sqrt(N) to
        // locate all of the prime numbers.
        for (int i = 2; i * i <= N; i++)
        {

            if (!isPrime[i])
            {
                continue;
            }

            // Iterate through all multiples of the prime and mark them as
            // not prime.
            for (int multiples = i*i; multiples <= N; multiples += i)
            {
                isPrime[multiples] = false;
            }

        }
        return isPrime;
    }

    //-----------Scanner class for faster input----------
    /* Provides similar API as java.util.Scanner but does not
     * use regular expression engine.  
     */
    public static class Scanner {
        BufferedReader br;
        StringTokenizer st;

        public Scanner(Reader in) {
            br = new BufferedReader(in);
        }

        public Scanner() { this(new InputStreamReader(System.in)); }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() { return Integer.parseInt(next()); }
        long nextLong() { return Long.parseLong(next()); }
        double nextDouble() { return Double.parseDouble(next()); }

        // Slightly different from java.util.Scanner.nextLine(),
        // which returns any remaining characters in current line,
        // if any.  
        String readNextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}
