35166번 - A. Nihilation 스페셜 저지다국어

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.