Задан массив 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.
Выходные данные
В первой строке выведите целое число k (0 ≤ k ≤ 5n) — количество использованных операций. Далее выведите сами операции. Каждая операция должна быть выведена в формате «i j» (1 ≤ i < j ≤ n; (j - i + 1) является простым числом).
Если существует несколько правильных ответов, разрешается вывести любой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 2 1
|
1
1 3
|
|
2
|
2
1 2
|
0
|
|
3
|
4
4 2 3 1
|
3
2 4
1 2
2 4
|