When trying to clean your old room, you find out your old notes from high school. Reading the homeworks you were given then, you start thinking how much easier they would have been today. However, there is a particular one that still seems to maintain its difficulty.

When the solution to a problem involved solving the square root of an integer, to keep a fancy and clean expression, you were asked to express it as the integer part and the root part. This means that if you had as solution N you were asked to express it as √N = A √B with the part A being as high as possible. For instance, 180 can be expressed as 1 √180, 2 √45, 3 √20 or 6 √5. Of course, the last expression is the correct one.

Now that you are grown up, you decide to write a program to perform this task for you.

Input

The input contains several test cases, each one described in a single line. The line contains an integer N (1 ≤ N ≤ 10¹⁸). The last line of the input contains a single −1 and should not be processed as a test case.

Output

For each test case output a single line with two integers A and B separated by a single space such that √N = A √B and A is maximum.

Example

Input:
180
17
1000000000000000000
-1
Output:
6 5
1 17
1000000000 1