说明

给定一个由 $N$ 个正整数组成的数组 $A = [A_1, A_2, \ldots, A_N]$。

在一次操作中，你可以选择整数 $m$ 和 $k$，满足 $1 \leq k < m \leq 10^9$，并对所有 $1 \leq i \leq N$ 将 $A_i$ 设置为 $(A_i \times k) \bmod 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$ 的操作序列中的一次操作。

如果存在多个满足条件的序列，输出其中任意一个即可。

5
4 1 2 6 3

2
12 6
3 2

2
9 9

1
3 1

提示

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

• $A_i := (A_i \times 6) \bmod 12 \implies A = [0, 6, 0, 0, 6]$
• $A_i := (A_i \times 2) \bmod 3 \implies A = [0, 0, 0, 0, 0]$

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

翻译由 DeepSeek V3.2 完成