Description

某外星国并没实行计划生育，决定选出幸运妈妈。具体如下： 假设妈妈生了N个孩子，若N能表示成某个正整数X的K次幂（K＞1），N可能有多种表示方法，找出最小的X并输出相应的K，你若找到，则政府将奖励那位妈妈，你帮她快速断定一下吧！ 例如 16＝2^4＝4^2,64＝4^3＝2^6=8^2则16应表示为2＾4，64应表示为2＾8。

Input

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

Output

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

Sample

Input

5
4
16
27
0

Output

0 0
2 2
2 4
3 3