题目描述

You are given an array $A = [A_1, A_2, \ldots, A_N]$ consisting of $N$ positive integers.

In one operation, you can choose integers $m$ and $k$ such that $1 \leq k < m \leq 10^9$ and set $A_i := (A_i \times k) \bmod m$ for $1 \leq i \leq N$.

What is the minimum number of operations needed to make all $A_i$ equal to $0$?

Output any sequence of operations to be done. It can be proven that it is always possible to make all $A_i$ equal to $0$.

输入格式

Input begins with an integer $N$ ($1 \le N \le 100\,000$). The next line contains $N$ integers $A_i$ ($1 \le A_i \le 10^9$) representing the given array $A$.

输出格式

In the first line, output the minimum number $q$ of operations needed.

In the next $q$ lines, output two integers $m$ and $k$, representing the operation in the sequence of operations that makes all $A_i$ equal to $0$.

If there are multiple such sequences, output any one of them.

5
4 1 2 6 3

2
12 6
3 2

2
9 9

1
3 1

提示

$\textit{Explanation of Sample 1:}$ The following describes the sequence of operations done in the sample output.

• $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]$

It can be shown that no sequence of operations with length $1$ can make all $A_i$ equal to $0$.