HOMEW - Homework

no tags 

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 ≤ 1018 ). 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: 2016-10-14 08:17:08

Be careful with squares of primes.

rainy jain : 2016-05-23 03:16:08

@Pablo my algorithm seems efficient but I'm getting WA. Please check.

prash1: 2016-02-25 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): 2016-02-04 20:50:05

Do not need factorize the number completly only until the cube root

ashish kumar: 2016-01-02 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:2010-08-24
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