Sum of Cubes

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 3113
64-bit integer IO format: %I64d      Java class name: Main

Description

According to Goldbach’s conjecture, every even number can be expressed as a sum of two odd primes. Which numbers can be expressed as the sum of two cubes?

Input

For each test case, a line will contain a positive integer n which will be at most one million.

The last line will contain the integer 0, which should not be processed.

Output

For each test case, output two integers x and y such that x3 + y3 = n. If there are many such pairs of numbers, choose x to be as small as possible. If there are no such pairs, output “Impossible”.

Sample Input

1
2
3
1000000
0

Sample Output

0 1
1 1
Impossible
0 100

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .