F. Fuzzy Factorization
time limit per test
0.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Finding the prime factorization of big numbers is a challenging task. It is so difficult that the security of almost our entire digital world, from online banking to private messages, is built upon how hard it is. In this problem, you are asked to perform such a factorization, but some relative error is allowed in your answer.

More formally, you are given an integer $$$X$$$, and you have to provide the prime factorization of any number $$$Y = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$$$ such that

  • the relative error of the factorization does not exceed $$$10^{-9}$$$ (that is, $$$\frac{|X-Y|}{X} \leq 10^{-9}$$$), and
  • each prime factor $$$p_i$$$ of $$$Y$$$ does not exceed $$$10^{18}$$$ (that is, $$$p_i \leq 10^{18}$$$ for $$$i = 1, 2, \ldots, k$$$).
Input

The input consists of an integer $$$X$$$ ($$$2 \leq X \leq 10^{1000}$$$).

Output

The first line must contain a positive integer $$$k$$$ indicating the number of different prime factors in the prime factorization of $$$Y = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$$$.

The $$$i$$$-th of the next $$$k$$$ lines must contain the two positive integers $$$p_i$$$ and $$$e_i$$$, representing that $$$p_i$$$ is a prime factor of $$$Y$$$ with multiplicity $$$e_i$$$.

It can be proven that a valid answer exists under the given constraints. If there are multiple solutions, output any of them.

Examples
Input
520
Output
3
2 3
5 1
13 1
Input
1073741825
Output
5
5 2
13 1
41 1
61 1
1321 1
Note

Explanation for example 2

$$$X=1073741825$$$, $$$Y=2^{30}=1073741824$$$, and the relative error is $$$\frac{|X-Y|}{X} = \frac{1}{1073741825} \le 10^{-9}$$$.

Note that there are other valid solutions for this test case.