Description

输入一个大于 1 的整数 n，按从小到大的顺序输出它的质因子及其指数。

Input Format

一行一个整数 n。

Output Format

若 n=p1^a1p2^a2...，每行输出一个质因子和指数。

60

2 2
3 1
5 1

Hint

试除法分解，循环条件可以写 i*i<=n，最后如果 n>1，n 本身是一个质因子。