给定一个包含 $N$ 个正整数的数组 $A = [A_1, A_2, \dots, A_N]$。

在一次操作中，你可以选择整数 $m$ 和 $k$，使得 $1 \le k < m \le 10^9$，并将所有 $1 \le i \le N$ 的 $A_i$ 更新为 $A_i := (A_i \times k) \pmod m$。

求使所有 $A_i$ 变为 $0$ 所需的最少操作次数。输出任意一组满足条件的操作序列。可以证明，总能使所有 $A_i$ 变为 $0$。

输入格式

输入的第一行包含一个整数 $N$ ($1 \le N \le 100\,000$)。下一行包含 $N$ 个整数 $A_i$ ($1 \le A_i \le 10^9$)，表示给定的数组 $A$。

输出格式

在第一行，输出所需的最少操作次数 $q$。

在接下来的 $q$ 行中，每行输出两个整数 $m$ 和 $k$，表示操作序列中的一次操作，使得所有 $A_i$ 最终变为 $0$。如果存在多种这样的序列，输出其中任意一个即可。

样例

输入 1

5
4 1 2 6 3

输出 1

2
12 6
3 2

说明 1

以下描述了样例输出中的操作序列：

1. $A_i := (A_i \times 6) \pmod{12} \implies A = [0, 6, 0, 0, 6]$
2. $A_i := (A_i \times 2) \pmod 3 \implies A = [0, 0, 0, 0, 0]$

可以证明，不存在长度为 $1$ 的操作序列能使所有 $A_i$ 变为 $0$。

输入 2

2
9 9

输出 2

1
3 1