整数的分解

一个正整数n可以分解成如下形式 n=a_1^{n_1} * a_2^{n_2}*a_3^{n_3}* ... * a_k^{n_k}， 规定a_1< a_2 < ... < a_k，就可以得到n的唯一分解形式。

比如48=2^4*3^1。

输入一个正整数n(2<=n< 1e9)

输出k行。

第i行为两个数，a_i和n_i，中间用空格隔开。