Multiplicative Persistence Backtrace

This task shouldn't be quite difficult, but regard it rather as motivation for research! Thanks to our colleague Kostis K. for suggesting the topic of Multiplicative Persistence as an idea for a problem!

As we have got a bit tired of various tasks about "sum of digits" let's study another integer function, namely "product of digits". It works quite obviously:

PoD(314159) = 3*1*4*1*5*9 = 540

It is evident, that PoD is always reducing the number, i.e. PoD(x) < x. (Well, it's not that evident - try to prove it yourself). And hence consequtive application of PoD several times should eventually bring us to single digit value. For example:

3777899 => 666792 => 27216 => 168 => 48 => 32 => 6

How long such chain could be? Surprisingly, that is not known yet! However no one yet found a chain longer than 11 steps. The length of the chain (number of times PoD applied) is called Multiplicative Persistence for the given number.

Generalization

Properties of numbers related to their digits are, of course, dependent on the choice of numeral system. For PoD function we may expect that larger numeral system base gives less chance of chain halting to 0. But moreover it seems that prime bases are much more fruitful.

Let's try to investigate the task in reverse! Given some small value Y, let's find some larger value X which comes to that Y after certain number of PoD applications. E.g. given 32 as target number, base 10 for calculations and 5 steps - one of the answers could be 3777899 as in example above. Or in base 23, start value F and 9 steps the answer DEEM is suitable. Chains of 11 steps could be found easily in base 23 too - and supposedly longer ones! :)

Problem Statement

Input data will give an amount N of testcases in the first line.
Next lines will give single testcase each, in the form Y B K where Y is target, B base of numeral system and K is amount of steps. Of them 10 <= B <= 36, Y <= B*B, K <= 7.

Answer should contain N source values X, such that PoD applied K times to this X will yield corresponding Y (both Y and X written in base B).

Example

input:
3
A 25 7
34 20 6
28 14 7

answer:
HHHIIN 377BGGIJ 2ACDDDDD