P15655 [ICPC 2025 Jakarta R] 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.

$\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$.