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.util.*;
import java.awt.Point;
import java.io.*;
import java.math.BigInteger;

public class C2
{
    FastScanner in;
    PrintWriter out;
            
    public class ErastofenBitSet 
    {
        int  n;
        byte mas[];

        public ErastofenBitSet(int n)
        {
            super();
            this.n = n;
            
            mas = new byte[n / 8 + 1];
            
            mas[0] = 3;
            
            for(int i = 2; i * i < n; i++)
            {
                if(getBit(i) == 0)
                {
                    for(int j = i * i; j < n; j += i)
                        setBit(j, (byte)1);
                }
            }
        }
        
        byte getBit(int pos)
        {
            return (byte)((mas[pos / 8] >> (pos % 8)) & (byte)1);
        }
        
        void setBit(int pos, byte val)
        {
            mas[pos / 8] |= 1 << (pos % 8);
        }
    }
    
    public class Node implements Comparable<Node>
    {
        int index;
        int value;
        
        public Node(int index, int value)
        {
            this.index = index;
            this.value = value;
        }

        @Override
        public int compareTo(Node o)
        {
            int ret = Integer.compare(value, o.value);
            
            if(ret == 0)
                ret = Integer.compare(index, o.index);
            
            return ret;
        }
    }
    
    public void solve() throws IOException
    {
        int n       = in.nextInt();
        
        ErastofenBitSet era = new ErastofenBitSet(n + 1);
        
        Node                   mas[]  = new Node[n];
        Node                   mas2[] = new Node[n];
        
        for(int i = 0; i < n; i++)
        {
            mas[i]  = new Node(i, in.nextInt());
            mas2[i] = mas[i];
        }
        
        Arrays.sort(mas);
        
        TreeSet<Integer> ts = new TreeSet<Integer>();
        
        for(int i = 2; i <= n; i++)
        {
            if(era.getBit(i) == 0)
            {
                ts.add(i);
            }
        }
        
        ArrayList<Point> ar = new ArrayList<Point>();
        
        for(int i = 0; i < n; i++)
        {
            int index = mas[i].index;
            
            if(index != i)
            {
                int dif = index - i + 1;
                
                while(dif > 1)
                {
                    int dif2 = ts.floor(dif);
                                        
                    dif -= dif2 - 1;
                    
                    int tmp = mas[i].index;
                    int to  = mas[i].index - (dif2 - 1);
                    
                    mas[i].index     = to;
                    mas2[to].index   = tmp;
                    
                    mas2[tmp] = mas2[to];
                    mas2[to]  = mas[i];
                    
                    ar.add(new Point(to + 1, tmp + 1));                 
                }
            }
        }
        
        out.println(ar.size());
        
        for(Point point : ar)
        {
            out.println(point.x + " " + point.y);
        }   
    }

    public void run()
    {
        try
        {
            in = new FastScanner();
            out = new PrintWriter(System.out);

            solve();

            out.close();
        }
        catch (IOException e)
        {
            e.printStackTrace();
        }
    }

    class FastScanner
    {
        BufferedReader  br;
        StringTokenizer st;

        FastScanner()
        {

            br = new BufferedReader(new InputStreamReader(System.in));

        }

        FastScanner(File f)
        {
            try
            {
                br = new BufferedReader(new FileReader(f));
            }
            catch (FileNotFoundException e)
            {
                e.printStackTrace();
            }
        }

        String next()
        {
            while (st == null || !st.hasMoreTokens())
            {
                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());
        }

        int[] nextIntArray(int size)
        {
            int[] array = new int[size];

            for (int i = 0; i < size; i++)
            {
                array[i] = nextInt();
            }

            return array;
        }

        long[] nextLongArray(int size)
        {
            long[] array = new long[size];

            for (int i = 0; i < size; i++)
            {
                array[i] = nextLong();
            }

            return array;
        }

        BigInteger nextBigInteger()
        {
            return new BigInteger(next());
        }

        Point nextIntPoint()
        {
            int x = nextInt();
            int y = nextInt();
            return new Point(x, y);
        }

        Point[] nextIntPointArray(int size)
        {
            Point[] array = new Point[size];

            for (int index = 0; index < size; ++index)
            {
                array[index] = nextIntPoint();
            }

            return array;
        }

        List<Integer>[] readGraph(int vertexNumber, int edgeNumber, boolean undirected)
        {
            List<Integer>[] graph = new List[vertexNumber];

            for (int index = 0; index < vertexNumber; ++index)
            {
                graph[index] = new ArrayList<Integer>();
            }

            while (edgeNumber-- > 0)
            {
                int from = nextInt() - 1;
                int to = nextInt() - 1;

                graph[from].add(to);
                if (undirected)
                    graph[to].add(from);
            }

            return graph;
        }
    }

    public static void main(String[] arg)
    {
        new C2().run();
    }
}