你有一个数组 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) 是素数)。
如果有多个答案,您可以打印其中任何一个。
示例
输入 #1
3 3 2 1
输出 #1
1 1 3
输入 #2
2 1 2
输出 #2
0
输入 #3
4 4 2 3 1
输出 #3
3 2 4 1 2 2 4