PROG0428 - Rondo

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.

rondo
Typical tonal structure of the classical seven-part rondo used during the late 18th and early 19th century.

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

Een rondo (ook: rondeau of rondeel) is een vers- en muziekvorm die ontstaan is tijdens de middeleeuwen, waarbij een hoofdthema — het zogenaamde rondothema — telkens als een soort refrein terugkeert. De tussenliggende delen, die andere thema's bespelen, worden dan de coupletten genoemd. Tijdens het classicisme was de opeenvolging van refreinen en coupletten vaak symmetrisch, en werden patronen gebruikt van de vorm ABA of ABACABA.

rondo
Typische tonale structuur van de klassieke zevendelige rondo zoals die gebruikt werd eind achttiende begin negentiende eeuw.

Dit soort symmetrische patronen kan makkelijk geconstrueerd worden op basis van de volgende procedure. De procedure start met de meest eenvoudige vorm A van een symmetrisch patroon, die het hoofdthema voorstelt. Het volgende patroon wordt steeds bekomen door de volgende letter van het alfabet aan het vorige patroon toe te voegen, en daarachter nogmaals het vorige patroon te herhalen. Op die manier krijgen we achtereenvolgens A, ABA, ABACABA, ABACABADABACABA, ….

Veronderstel dat we bovenstaande constructieprocedure lang genoeg blijven herhalen totdat we een symmetrisch rondopatroon krijgen van de vorm ABACABADABACABA…. Wat is dan het deelpatroon dat start op positie $p$ en $l$ delen lang is?

Invoer

De eerste regel van de invoer bevat een getal $t \in \mathbb{N}$ dat aangeeft hoeveel gevallen er volgen. Daarna volgen nog $2t$ regels, omdat elk geval omschreven wordt door twee getallen $p, l \in \mathbb{N}$ die elk op een afzonderlijke regel staan. Hierbij geldt dat $p \leq 5000$ en $l \leq 20$.

Uitvoer

Schrijf voor elk geval het deelpatroon uit van een voldoende lang symmetrisch rondopatroon dat start op positie $p$ en $l$ delen lang is. Hierbij spreken we af dat het eerste refrein A van het symmetrisch rondopatroon op positie 1 staat.

Voorbeeld

Invoer:

3
3
1
6
4
7
5

Uitvoer:

A
BADA
ADABA

Added by:Peter Dawyndt
Date:2013-09-11
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:PY_NBC
Resource:None

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.