Sum of Cubes

0

0 votes
Medium
Problem

Any positive integer x can be expressed as a sum of a finite number of cubes x=d31+d32+....+d3k where 1<i<k and di is a positive integer. Your task is to minimize the value of k.

To illustrate, 3=13+13+13 (k is 3), 28=33+13 (k is 2), and 125=53 (k is 1).

INPUT

The input starts with a positive number n followed by n positive integers. The positive integers are separated by whitespaces. Each positive integer x is less than or equal to a million.

OUTPUT

For each non-negative integer x, you have to output x and the minimum k as defined above. Each of the pair of values x k should appear in one output line.

SAMPLE INPUT

3
3 28 125

SAMPLE OUTPUT

3 3
28 2
125 1
Time Limit: 5
Memory Limit: 256
Source Limit:
Editor Image

?