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