Inconstant Ordering

Interview

Time limit10sMemory limit1024 MB

Summary

Given block sizes, build the alphabetically smallest string starting with A where letters strictly increase in odd blocks and strictly decrease in even blocks.

Level: Medium6 of 10
Topics: Greedy, String, Implementation, Math
Solved: No attempts yet

Problem

We want to build a string of uppercase English letters in sorted order. However, we want the order to be sometimes strictly increasing and sometimes strictly decreasing.

The first letter of the string must be A. After that, the string must contain one or more blocks of letters. The $i$ -th block must contain exactly $L_i$ letters. If $i$ is odd, each letter in the $i$ -th block must be later in the alphabet than its preceding letter in the string; if $i$ is even, it must be earlier in the alphabet than its preceding letter. Note that the first letter of a block also has a preceding letter, even though that letter is not in the block. A string that follows all of these rules is called valid. There can be multiple valid strings, and we want to find the alphabetically first one.

For example, if there are $2$ blocks of sizes $L_1=2$ and $L_2=3$ , the string must have exactly $1+L_1+L_2=1+2+3=6$ letters (the $1$ is for the initial A). The strings XYZYBA, AZYCBA, and AYZYBB are not valid for this case because they violate the required starting letter condition, and the ordering conditions in the first and second block, respectively. The string AYZYBA is valid. The string ABDCBA is also valid and, moreover, it is the alphabetically first valid string.

Given the sizes of the blocks, output the valid string that comes first in alphabetical order among all valid strings. It can be shown that, for all inputs within the given limits, at least one valid string exists.

Input

The first line of the input gives the number of test cases, $T$ . $T$ test cases follow. Each test case is described with two lines. The first line of a test case contains a single integer $N$ , the number of blocks. The second line contains $N$ integers $L_1,L_2, \cdots ,L_N$ , the number of letters each block must have, in order.

Output

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the valid string that comes first in alphabetical order. It is guaranteed that at least one valid string exists.

Limits

$1≤T≤100$ .
$1≤L_i≤25$ , for all $i$ .

Examples1

Example 1

Input

Expected output

Case #1: ABDCBA
Case #2: ABCDEFA
Case #3: ABC