Description

最近Catcher对数字游戏很感兴趣，他发明了一种新的游戏：给出一个数N，问N是否能表示成某个正整数X的K次幂（K＞1），N可能有多种表示方法，请找出最大的X并输出相应的K。例如 16＝2^4＝4^2,64＝4^3＝2^6=8^2则16应表示为4＾2，64应表示为8＾2。

Input

每行一个正整数N（0＜N＜10^8），输入文件以0为结束标志。

Output

每行有两个整数，如果能表示，则输出X　K（中间用一个空格隔开），反之，则输出0　0。

Sample

Input

5
4
16
27
0

Output

0 0
2 2
4 2
3 3

Source: qn