Power Sum of Digits

Thanks to Clive Fraser for this problem!

We will define a Special Number as a positive integer where the sum of its digits is a^b; where a and b are any positive integers greater than 1.

The first 5 special numbers are 4, 8, 9, 13 and 17. Of them 4, 8 and 9 are single-digit numbers so the sum of digits is equal to the number itself. Note that 4 = 2^2, 8 = 2^3 and 9 = 3^2. The 2-digit numbers 13 and 17 have digit sums of 4 = 2^2 and 8 = 2^3.

Some other examples of special numbers are: 79 (digit sum 16 = 2^4), 799 (digit sum 25 = 5^2) and 999 (digit sum 27 = 3^3).

If we put all of the special numbers into size order, we can associate each number with its position in the list. For example 4 is at position 1, 17 is at position 5 and 999 is at position 191.

You will be given a number of positions (n) in the list and are asked to determine the special numbers which are at those positions. The position (n) will always be smaller than 5 x 10^17.

Input/Output description: The first line of the input data will contain a single integer K, the number of problems to solve. K lines will follow. Each line contains a single integer n, the position in the special number list. You need to find the special number at this position. Combine all of your answers into a single string, separated by spaces.

Example:

input:
5
5
191
640
8944
179161

answer:
17 999 3616 52965 896045