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
//package R246_D2;
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

import java.math.*;
import java.io.*;
import java.text.*;
import java.util.*;
 
public class C {
//    private static final String INPUT_PATH = "C:\\atcoder\\b_008_004.txt";
    private static final String INPUT_PATH = null;

    String getKey(int[] i) {
        StringBuilder sb = new StringBuilder();
        for (int s : i) {
            sb.append(" " + s);
        }
        return sb.toString();
    }
    
    public void newSolve() {
        try {
            br = new BufferedReader(new InputStreamReader(
                    INPUT_PATH == null ? System.in : new FileInputStream(new File(INPUT_PATH))));

            Integer[] primes = getPrimeNum();

            int N = readInt();

            int[][] a = new int[N][];
            for(int i = 0;i < N;i++){
                a[i] = new int[]{readMinInt(), i};
            }
            
            Arrays.sort(a, new Comparator<int[]>() {
                public int compare(int[] a, int[] b) {
                    return a[0] - b[0];
                }
            });

            int[] ia = new int[N];
            for(int i = 0;i < N;i++)ia[a[i][1]] = i;
            List<String> lines = new ArrayList<String>();
            for(int i = 0;i < N;i++){
                int x = a[i][1];
                while(x > i){
                    int ind = Arrays.binarySearch(primes, x-i+1);
                    if(ind < 0)ind = -ind-2;
                    lines.add((x-primes[ind]+1+1) + " " + (x+1));
                    int nex = x-primes[ind]+1;
                    int num = ia[nex];
                    {int d = a[i][1]; a[i][1] = a[num][1]; a[num][1] = d;}
                    {int d = ia[x]; ia[x] = ia[nex]; ia[nex] = d;}
                    x = nex;
                }
            }
            pw.println(lines.size());
            for(String line : lines){
                pw.println(line);
            }

        } catch(Exception e) {
            e.printStackTrace();
        } finally {
            try {
                br.close();
            } catch (Exception igunore) {}
        }
        
    }
    
    public void solve() { 
        try {
            br = new BufferedReader(new InputStreamReader(
                    INPUT_PATH == null ? System.in : new FileInputStream(new File(INPUT_PATH))));

            int N = readInt();

            int[] first = readIntArray();
            
            Integer[] prime = getPrimeNum();
            
            int[] goal = Arrays.copyOf(first, N);
            Arrays.sort(goal);

            int[] check = copyOf(first, N);

            int[][] test = new int[10][];
            test[0] = new int[]{1,2};
            System.out.println(test[0][0]);
            System.out.println(test[0][1]);
            
            int sortedIndex = 0;

            int[][] kits = new int[5 * N + 1][2];

            Set<String> set = new HashSet<String>();
            set.add(getKey(check));
            
            int sortCnt = 0;
            while(! deepEquals(check, goal) && sortCnt <= 5 * N) {
                boolean isUpdate = false;
                for (int i = sortedIndex; i < N - 1; i++) {
                    if (check[i] == i + 1) continue;
                    for (int j = i + 1; j < N; j++) {
                        if (check[j] == i + 1 && checkPrimeNum(abs(check[i] - check[j]) + 1)) {
                            kits[sortCnt][0] = min(check[i], check[j]);
                            kits[sortCnt][1] = max(check[i], check[j]);
                            
                            int tmp = check[i];
                            check[i] = check[j];
                            check[j] = tmp;
                            if (!set.add(getKey(check))) {
                                check[j] = check[i];
                                check[i] = tmp;
                                continue;
                            }
                            sortCnt++;
                            isUpdate = true;
                            
                            if (i == sortedIndex + 1) {
                                sortedIndex++;
                            }
                        }
                    }
                }

                if (!isUpdate) {
                    while (true) {
                        int c1 = (int) (random() * N);
                        int c2 = (int) (random() * N);
                        if (c1 == c2) continue;

                        if (checkPrimeNum(abs(check[c1] - check[c2]) + 1)) {
                            kits[sortCnt][0] = min(check[c1], check[c2]);
                            kits[sortCnt][1] = max(check[c1], check[c2]);
                            
                            int tmp = check[c1];
                            check[c1] = check[c2];
                            check[c2] = tmp;
                            if (!set.add(getKey(check))) {
                                check[c2] = check[c1];
                                check[c1] = tmp;
                                continue;
                            }
                            sortCnt++;

                            break;
                        }
                        
                    }
                }
                
            }

            System.out.println(sortCnt);
            int index = 0;
            for (int[] kit : kits) {
                if (index++ == sortCnt) break;
                pw.println(kit[0] + " " + kit[1]);
            }
            

        } catch(Exception e) {
            e.printStackTrace();
        } finally {
            try {
                br.close();
            } catch (Exception igunore) {}
        }
    }

    boolean[] dp = new boolean[100001];
    {
        Arrays.fill(dp, true);
        dp[0] = false;
        dp[1] = false;
        for (int i = 2; i <= 1000; i++) {
            if (dp[i]) {
                for (int j = i + i; j < 100001; j+=i ) {
                    dp[j] = false;
                }
            }
        }
    }
    boolean checkPrimeNum(int num) {
        return dp[num];
    }
    
    Integer[] getPrimeNum() {
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 2; i < 100000; i++) {
            if (checkPrimeNum(i)) list.add(i);
        }

        return list.toArray(new Integer[0]);
    }
    
    boolean deepEquals(int[] i1, int[] i2) {
        if (i1.length != i2.length) return false;
        for (int i = 0 ; i < i1.length; i++) {
            if (i1[i] != i2[i]) return false;
        }
        return true;
    }

    private int brPos = 0;
    private int[] brBuf = null;
    
    private int readMinInt() throws IOException {
        if (brBuf == null || brBuf.length == brPos) {
            brBuf = readIntArray();
            brPos = 0;
        }
        return brBuf[brPos++];
    }

    private int readInt() throws IOException {
        return Integer.parseInt(br.readLine());
    }

    private long readLong() throws IOException {
        return Long.parseLong(br.readLine());
    }

    private int[] readIntArray() throws IOException {
        String[] s = readStrArray();
        int cnt = s.length;
        int[] out = new int[cnt];
        for (int i = 0; i < cnt; i++) {
            out[i] = Integer.parseInt(s[i]);
        }
        return out;
    }

    private Integer[] convIntArray(int[] arg) {
        int len = arg.length;
        Integer[] res = new Integer[len];
        for (int i = 0; i < len; i++) {
            res[i] = arg[i];
        }
        return res;
    }
    
    private long[] readLongArray() throws IOException {
        String[] s = readStrArray();
        int cnt = s.length;
        long[] out = new long[cnt];
        for (int i = 0; i < cnt; i++) {
            out[i] = Long.parseLong(s[i]);
        }
        return out;
    }

    private String[] readStrArray() throws IOException {
        String[] s = br.readLine().split(" ");
        return s;
    }

    void permutationAll(int[] p) {
        permutation(p, 0, p.length - 1);
     }
    
    void permutationRange(int from, int to) {
        int cnt = to - from + 1;
        int[] elements = new int[cnt];
        for (int i = 0 ; i <  cnt; i++) {
            elements[i] = from++;
        }
        permutation(elements, 0, cnt - 1);
    }

    void permutationString(String element) {
        char[] elements = element.toCharArray();
        permutationString(elements, 0, elements.length - 1);
    }

    
    void permutation(int[] elements, int nowCnt, int totalCnt) {
        if (nowCnt == totalCnt) { 

            // TODO insertCode
        } else {
            
          for (int i = nowCnt; i <= totalCnt; i++) {
            int tmp = elements[nowCnt]; 
            elements[nowCnt] = elements[i]; 
            elements[i] = tmp;
            permutation(elements, nowCnt+1, totalCnt);
            tmp = elements[nowCnt]; 
            elements[nowCnt] = elements[i]; 
            elements[i] = tmp;
          }
        }
     }

    void permutationString(char[] elements, int nowCnt, int totalCnt) {
        if (nowCnt == totalCnt) { 
            
            // TODO insertCode
        } else {
            
          for (int i = nowCnt; i <= totalCnt; i++) {
            char tmp = elements[nowCnt]; 
            elements[nowCnt] = elements[i]; 
            elements[i] = tmp;
            permutationString(elements, nowCnt+1, totalCnt);
            tmp = elements[nowCnt]; 
            elements[nowCnt] = elements[i]; 
            elements[i] = tmp;
          }
        }
     }

    
    private static long gcd(long n1, long n2) {
        return (n2 == 0)?n1:gcd(n2, n1%n2);
    }
    private static int gcd(int n1, int n2) {
        return (n2 == 0)?n1:gcd(n2, n1%n2);
    }

    public static void main(String[] args) {
        long from = System.currentTimeMillis();
        C app = new C();
        app.newSolve();
        pw.flush();
        pw.println(System.currentTimeMillis() - from);
    }

    void printInt(int[] p) {
        for (int i : p) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

   void debug(Object ... o) {
       pw.write(deepToString(o));
   }
   BufferedReader br = null;
   static PrintWriter pw = new PrintWriter(System.out);

   class Type {
       int x, y;
       
       Type (int x, int y) {
           this.x = x;
           this.y = y;
       }
       
   }
}