Sanket is a math geek, he recently found out about numbers known as narcassictic numbers.
A n-digit Narcissistic Number is a number such that sum of its digits raised to the nth power is the number itself.
For example excluding the trivial 1-digit numbers the smallest Narcissistic number is 153 because 153 = 13 + 53 + 33.
As this piqued Sanket's interest now he wants to find out what is the minimum number of numbers required whose sum after raising them
to power k (where k is the number of digits in the given number) equals the given number.
As Sanket has other responsibilities bestowed upon him by his older brother, he being logical asks you help him out ??
Input
First line contain a single number T denoting the number of test cases.
Next T lines contains one integer N per line.
Output
For each test case output a single number
Input Constraint
1 ≤ T ≤ 103
1 ≤ N ≤ 106
Sample Explanation
153 is a 3 digit number.
153 = 153 x 13
153 = 13 + 33 + 53
Minimum 3 numbers are required whose cube sum upto 153.
