Description

AsindE 有一个长为 $n$ 的数组 $a = [p, p + 1, \cdots, p + n - 1]$，其中数组下标从 $1$ 开始，$p$ 为质数。

一天，AsindE 发现数组 $a$ 被 slwang 重新排列了，AsindE 想使数组 $a$ 恢复原状，为此他每次可以选择两个互质的数，交换它们在数组中的位置。比如，数组 $a=[2,3,4,5]$，选择数字 $3$ 和 $2$ 交换它们在数组中的位置后：$a=[3,2,4,5]$。

AsindE 希望用至多 $2n$ 次交换使数组 $a$ 递增，请你帮助他。

Format

Input

第一行一个正整数 $n$ $(1 \leq n \leq 10^5)$，表示数组 $a$ 的长度。

第二行 $n$ 个正整数 $a_1, a_2, \cdots, a_n$ $(2 \leq a_i \leq 10^9)$，表示重新排列后的数组 $a$。保证 $a_i$ 最小值为质数 $p$，且范围在 $[p, p + n - 1]$ 中的整数均在数组 $a$ 中出现一次。

Output

第一行输出一个整数 $k$ $(0 \leq k \leq 2n)$，表示交换次数。

接下来应输出 $k$ 行，每行两个正整数 $i, j$ $(1 \leq i,j \leq n; i \neq j)$，满足 $\gcd(a_i, a_j) = 1$，表示将 $a_i$ 与 $a_j$ 交换。

只要你的程序输出合法且按输出先后顺序进行交换后能使数组 $a$ 递增即可通过本题。

Samples

6
3 5 4 7 8 6

3
2 3
4 6
5 6

4
233 234 235 236

0

Note

第一个样例按顺序交换过程如下：

• 交换 $a_2, a_3$ 后，$a=[3, \underline{4}, \underline{5}, 7, 8, 6]$；
• 交换 $a_4, a_6$ 后，$a=[3, 4, 5, \underline{6}, 8, \underline{7}]$；
• 交换 $a_5, a_6$ 后，$a=[3, 4, 5, 6, \underline{7}, \underline{8}]$。

Limitation

1s, 1024KiB for each test case.