Dado un entero \(X\), entrega la factorización prima de algún entero \(Y = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}\) que cumpla:

• error relativo a lo más \(10^{-9}\), es decir, \(\dfrac{|X - Y|}{X} \le 10^{-9}\), y
• cada primo \(p_i \le 10^{18}\).

Se puede demostrar que siempre existe una respuesta válida.

Entrada

Una línea con un entero \(X\) \((2 \le X \le 10^{1000})\).

Salida

La primera línea debe tener un entero positivo \(k\): la cantidad de primos distintos de la factorización de \(Y\). Cada una de las siguientes \(k\) líneas tiene dos enteros positivos \(p_i\) y \(e_i\): un primo y su multiplicidad.

Si hay varias respuestas, cualquiera es aceptada.

Notas

En el segundo ejemplo, \(X = 1073741825\) y \(Y = 2^{30} = 1073741824\), con error relativo \(1/1073741825 \le 10^{-9}\).

Ejemplo 1

Entrada

520

Salida

3
5 1
2 3
13 1

Ejemplo 2

Entrada

1073741825

Salida

1
2 30

Regional Latinoamericana 2025 del ICPC, problema F («Fuzzy Factorization»). Versión en español redactada para este juez; el enunciado oficial, en inglés, está aquí abajo.