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.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;

public class C {

	static ArrayList<Integer> p = new ArrayList<>();
	static ArrayList<Integer> parent = new ArrayList<>();
	static ArrayList<String> ans = new ArrayList<>();

	static void prnt(int req) {
		parent.clear();
		int sum = req;
		int lo = 0;
		int hi = p.size() - 1;
		while (lo < hi) {
			int mid = (lo + hi) / 2;
			if (p.get(mid) - 1 < sum)
				lo = mid + 1;
			else
				hi = mid;
		}
		for (int i = lo; i > -1; i--) {
			int num = p.get(i) - 1;
			while (sum >= num) {
				sum -= num;
				parent.add(num);
			}
		}
	}

	static void print(int x, int y) {
		if (x > y) {
			int tmp = x;
			x = y;
			y = tmp;
		}
		ans.add((x + 1) + " " + (y + 1));
	}

	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		sc = new StringTokenizer("");
		boolean[] v = new boolean[100000];
		for (long i = 2; i * i < v.length; i++)
			if (!v[(int) i])
				for (long j = i * i; j < v.length; j += i)
					v[(int) j] = true;
		for (int i = 2; i < v.length; i++)
			if (!v[i])
				p.add(i);
		int n = nxtInt();
		int[] arr = new int[n];
		HashMap<Integer, Integer> hm = new HashMap<>();
		for (int i = 0; i < arr.length; i++) {
			arr[i] = nxtInt() - 1;
			hm.put(arr[i], i);
		}
		for (int i = n - 1; i > -1; i--) {
			if (hm.get(i) == i)
				continue;
			int reqLen = i - hm.get(i);
			prnt(reqLen);
			int x = hm.get(i);
			for (int j = 0; j < parent.size(); j++) {
				int step = parent.get(j);
				int idx = x + step;
				print(x, idx);
				int tmp = arr[x];
				arr[x] = arr[idx];
				arr[idx] = tmp;
				hm.put(arr[x], x);
				hm.put(arr[idx], idx);
				x = idx;
			}
		}
		out.println(ans.size());
		for (int i = 0; i < ans.size(); i++)
			out.println(ans.get(i));
		br.close();
		out.close();
	}

	static BufferedReader br;
	static StringTokenizer sc;
	static PrintWriter out;

	static String nxtTok() throws IOException {
		while (!sc.hasMoreTokens()) {
			String s = br.readLine();
			if (s == null)
				return null;
			sc = new StringTokenizer(s.trim());
		}
		return sc.nextToken();
	}

	static int nxtInt() throws IOException {
		return Integer.parseInt(nxtTok());
	}

	static long nxtLng() throws IOException {
		return Long.parseLong(nxtTok());
	}

	static double nxtDbl() throws IOException {
		return Double.parseDouble(nxtTok());
	}

	static int[] nxtIntArr(int n) throws IOException {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = nxtInt();
		return a;
	}

	static long[] nxtLngArr(int n) throws IOException {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nxtLng();
		return a;
	}

	static char[] nxtCharArr() throws IOException {
		return nxtTok().toCharArray();
	}
}