Sum of Cubes

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

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

Hint

lcy

Source

IPCP 2005 Northern Preliminary for Northeas

提交代码