C. Простые обмены
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Задан массив a[1], a[2], ..., a[n], элементами которого являются различные целые числа от 1 до n. Требуется отсортировать по возрастанию этот массив используя следующую операцию (возможно, несколько раз):

  • выбрать два индекса i и j (1 ≤ i < j ≤ n; (j - i + 1) является простым числом);
  • выполнить обмен элементов на позициях i и j местами; другими словами, разрешается выполнить следующую последовательность присвоений tmp = a[i], a[i] = a[j], a[j] = tmp (tmp — временная переменная).

Вам не требуется минимизировать количество используемых операций, тем не менее требуется, чтобы их было не более 5n.

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 105). В следующей строке записаны n различных целых чисел a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ n).

Выходные данные

В первой строке выведите целое число k (0 ≤ k ≤ 5n) — количество использованных операций. Далее выведите сами операции. Каждая операция должна быть выведена в формате «i j» (1 ≤ i < j ≤ n; (j - i + 1) является простым числом).

Если существует несколько правильных ответов, разрешается вывести любой.

Примеры
Входные данные
3
3 2 1
Выходные данные
1
1 3
Входные данные
2
1 2
Выходные данные
0
Входные данные
4
4 2 3 1
Выходные данные
3
2 4
1 2
2 4