HOMEW  Homework
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^{18} ). 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
hide comments
mahmud2690:
20161014 08:17:08
Be careful with squares of primes. 

rainy jain :
20160523 03:16:08
@Pablo my algorithm seems efficient but I'm getting WA. Please check. 

prash1:
20160225 15:19:49
can anyone tell me where i am wrong .my code is working on my machine properly but here gives wrong answer .my submission id is 16362490


Yosvany (BeCrazy):
20160204 20:50:05
Do not need factorize the number completly only until the cube root 

ashish kumar:
20160102 06:13:00
I am using Pollard rho's prime factorization but then also TLE. please check my code @author 
Added by:  Pablo Ariel Heiber 
Date:  20100824 
Time limit:  51.85s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS OBJC PERL6 VB.NET 
Resource:  FCEyN UBA ICPC Selection 2009 