Multiply or Add

After a while Jack and Jill decide to switch roles so that now Jill is choosing the numbers and Jack must develop the correct sequence. However they have become quite bored with the Double or Add game, and so they decide to modify the rules slightly:

• Jill begins by stating her chosen number n, along with another integer m
• Jack always starts at the number 0.
• Each turn, Jack can perform one of two actions, either
  • Multiply the current number by m, or
  • Add some value between 1 and m - 1 to the current number.
• However he added the previous turn, then Jack must multiply on the next turn. That is, he cannot perform two "add" actions consecutively.

The first move cannot be 0 -> 0.

For example if Jill states n = 46 and m = 3, then Jack can perform a sequence of actions to the number 0 which yields the desired number:

0 -> 1 -> 3 -> 5 -> 15 -> 45 -> 46

Note that any move from 1 -> m should be regarded as multiplication rather than addition.

If we refer to the doubling as action A, addition of 1 action B, addition of 2 to be action C, and continue to follow the same pattern with the remainder of the alphabet, then we can describe this sequence with the string:

BACAAB

Problem Statement

Input Data
First line will be Q, the quantity of testcases.
Q lines will then follow, each with a testcase in the format n m.

Answer
Should consist of Q space-separated strings corresponding the to the sequence of actions taken by Jack to produce the number n, starting from 0.

Example

input data:
3
46 3
135792468 14
246897531 26

answer:
BACAAB BAEAAGALAAKA UAUAHALAAX