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.ArrayList;
import java.util.List;

/**
 * Created by wencan on 2015/6/9.
 */
public class PrimeSwaps {
    BufferedWriter writer;

    public static void main(String[] args) throws IOException {
        PrimeSwaps swaps = new PrimeSwaps();
        swaps.resolve();
    }

    private void resolve() throws IOException {
        Reader reader = new Reader(System.in);

        int n = reader.nextInt();
        int[] a = new int[n];
        int[] p = new int[n + 1];
        int next;
        for (int i = 0; i < n; i++) {
            next = reader.nextInt();
            a[i] = next;
            p[next] = i;
        }

        System.in.close();

//        int n = 100000;
//        int[] a = new int[n];
//        int[] p = new int[n + 1];
//        for (int i = 0; i < n; i++) {
//            a[i] = n - i;
//            p[n-i] = i;
//        }

        primeList(n);
        int size = primes.size();
        while (size > 1) {
            if (primes.get(size - 1) <= n) break;
            else {
                primes.remove(size - 1);
                size--;
            }
        }

        List<Data> oper = new ArrayList<Data>();
        System.out.println(step(n, a, p, oper));
        for (Data data : oper) {
            System.out.println(data.i + " " + data.j);
        }

    }

    private int step(int n, int[] a, int[] p, List<Data> oper) throws IOException {
        int count = 0;
        int diff;
        int step;
        int size = primes.size();
        int pos;
        int rank;


        int guard = 1;
        while (true) {
            if (guard == n) break;

//            diff = guard - p[guard] - 1;
            diff = p[guard] - guard + 1;
            pos = p[guard];
            while (diff > 0) {
                rank = rank(primes, 0, Math.min(diff, size-1), diff+1);
                step = primes.get(rank) - 1;
                exch(a, pos, pos - step);
                p[a[pos]] = pos;
                p[a[pos - step]] = pos - step;
                oper.add(new Data( pos - step + 1, pos + 1));
                pos -= step;
                diff -= step;
                count++;
            }
            p[a[pos]] = pos;
            guard++;

        }

        return count;
    }


    private void exch(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    private int rank(List<Integer> list, int low, int hi, int target) {
        while (low < hi) {
            int m = low + (hi - low) / 2;
            int cmp = target-list.get(m);
            if      (cmp < 0) hi = m - 1;
            else if (cmp > 0) low = m + 1;
            else return m;
        }
        if(list.get(low)>target && low>0) return low-1;
        return low;
    }


    List<Integer> primes = new ArrayList<Integer>();

    private List<Integer> primeList(int upper) {
        primes.add(2);
        primes.add(3);

        int temp = 6;
        while (temp < upper) {
            int sqrt = (int) Math.sqrt(temp) + 1;
            if (isPrime(temp - 1, sqrt)) primes.add(temp - 1);
            if (isPrime(temp + 1, sqrt)) primes.add(temp + 1);
            temp += 6;
        }

        return primes;
    }

    private boolean isPrime(int check, int sqrt) {
        for (int p : primes) {
            if (p > sqrt) break;
            if (check % p == 0) return false;
        }
        return true;
    }

    private class Data {
        int i;
        int j;

        public Data(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }

    private class Reader {
        StreamTokenizer tokenizer;

        public Reader(InputStream inputStream) {
            tokenizer = new StreamTokenizer(new BufferedReader(new InputStreamReader(inputStream)));
        }

        public int nextInt() throws IOException {
            tokenizer.nextToken();
            return (int) tokenizer.nval;
        }
    }


}
