A rondo (or its French part-equivalent rondeau) is a medieval poetical and musical form, that contains repetitions of a couplet separated by longer sections of poetry. The form has a principal theme (sometimes called the refrain) that alternates with one or more contrasting themes, generally called episodes or couplets. During the Classical period the succession of refrains and couplets usually was symmetric, with patterns like ABA or ABACABA.

This kind of symmetrical patterns can be constructed easily based on the following procedure. The procedure starts with the most simple form A of a symmetric pattern, representing the principal theme. Each time, the next pattern is obtained by appending the next letter of the alphabet to the previous pattern, followed by a second repetition of the previous pattern. As such we successively get the following series of patterns: A, ABA, ABACABA, ABACABADABACABA, ….

If we continue the above procedure long enough so that we get a symmetrical rondo pattern that has the form ABACABADABACABA…, then what is the subpattern that starts at position $$p$$ and has $$l$$ sections?

Input

The first line of the input contains an integer $$t \in \mathbb{N}$$ that indicates the number of cases that follow. This is followed by another $$2t$$ line, as each case is described by two integers $$p, l \in \mathbb{N}$$, each on a separate line. It always holds that $$p \leq 5000$$ and $$l \leq 20$$.

Output

For each case, write the subpattern of a sufficiently long symmetrical rondo pattern that starts at position $$p$$ and has $$l$$ sections. We agree upon the fact that the first refrain A of the symmetrical rondo pattern is on position 1.

Example

Input:

3
3
1
6
4
7
5

Output:

A
BADA
ADABA