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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class C432C {

    public static ArrayList<Integer> simpleNumbers() {
        return simpleNumbers(100001);
    }

    public static ArrayList<Integer> simpleNumbers(int capacity) {
        boolean[] row = new boolean[capacity];

        row[0] = false;
        row[1] = false;
        for (int index = 2; index < row.length; index++) {
            row[index] = true;
        }

        for (int number = 2; number * number < row.length; number++) {
            if (row[number]) {

                for (int index = number * number; index < row.length; index += number) {
                    row[index] = false;
                }
            }
        }

        ArrayList<Integer> simpleNumbers = new ArrayList<Integer>();

        for (int number = 0; number < row.length; number++) {
            if (row[number]) {
                simpleNumbers.add(number);
            }
        }
        return simpleNumbers;
    }

    interface Data {
        void init();
    }

    interface Readable {
        Data data();
    }

    interface Answer {
        void print();
    }

    interface Printable {
        Answer answer();
    }

    public static class Algorithm implements Readable, Printable {
        public int[] numbers;
        public int[] sortNumbers;
        public ArrayList<String> answer = new ArrayList<String>();

        public void run() {
            ArrayList<Integer> simpleNumbers = simpleNumbers();

            answer = new ArrayList<String>();
            for (int number = 0; number < sortNumbers.length; number++) {
                while (sortNumbers[number] > number) {

                    int index = Collections.binarySearch(simpleNumbers, sortNumbers[number] - number + 1);
                    if (index < 0) {
                        index = -1 * (index + 1) - 1;
                    }

                    int fromIndex = sortNumbers[number] - simpleNumbers.get(index) + 1;
                    int toIndex = sortNumbers[number];

                    answer.add((fromIndex + 1) + " " + (toIndex + 1));

                    sortNumbers[numbers[fromIndex]] = toIndex;
                    sortNumbers[numbers[toIndex]] = fromIndex;

                    int temp = numbers[fromIndex];
                    numbers[fromIndex] = numbers[toIndex];
                    numbers[toIndex] = temp;
                }
            }
        }

        private class InputData implements Data {

            @Override
            public void init() {
                BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
                String[] items;

                try {
                    int length = Integer.parseInt(reader.readLine());

                    items = reader.readLine().split(" ");
                    numbers = new int[items.length];
                    sortNumbers = new int[items.length];

                    for (int index = 0; index < items.length; index++) {
                        numbers[index] = Integer.parseInt(items[index]) - 1;
                        sortNumbers[numbers[index]] = index;
                    }

                } catch (IOException ioe) {
                    System.out.println(ioe);
                }
            }
        }

        private class OutputData implements Answer {

            @Override
            public void print() {
                System.out.println(answer.size());
                for (String line: answer) {
                    System.out.println(line);
                }
            }
        }

        @Override
        public Data data() {
            return new InputData();
        }

        @Override
        public Answer answer() {
            return new OutputData();
        }
    }

    public static void main(String[] args) {
        Algorithm algorithm = new Algorithm();

        algorithm.data().init();
        algorithm.run();
        algorithm.answer().print();
    }
}
