409891: GYM103828 D Ctrl+A+C+V

D. Ctrl+A+C+Vtime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

We will create a new folder, and inside it, we will add a text file with the name $$$S$$$, then we will repeat the following $$$n$$$ times:

1. Ctrl-A: Select all the files currently in the folder.
2. Ctrl-C: Copy all the selected files.
3. Ctrl-V: Paste the copied files in the same folder.

When the $$$n$$$ steps are over, we will sort all the files by their names in lexicographical order.

The files will be renamed as follows:

All copied files will have $$$-$$$C0000 added to the end of their names when being pasted.

For a file is being pasted, if there is another file that has the same name, instead of adding $$$-$$$C0000 we increase the counter of this suffix to be $$$-$$$C0001, and if there is still a file sharing the same name we keep increasing the counter until there is no file that has the same name.

See notes for more clarification.

You have to print the name of the file whose index is $$$k$$$ after sorting the renamed files, it is guaranteed that a solution exists for such $$$k$$$.

Input

The first line of the input contains one integer $$$t$$$ $$$(1\le t\le 10^3)$$$ the number of test cases.

The first line of each test case contains a string $$$S$$$ $$$(|S|\le 10)$$$ the initial filename. The second line of each test case contains two integers $$$n$$$ $$$(1\le n\le 10^3)$$$, $$$k$$$ $$$(1\le k\le 10^{17})$$$ the number of times to copy all the files and the index of the file that you are asked its name.

It is guaranteed that $$$k$$$ is less or equal to the number of files created after making $$$n$$$ copies as demonstrated previously.

Output

For each test case print a single string $$$F$$$ the filename at index $$$k$$$ after sorting all the filenames in lexicographical order.

ExampleInput

2
Acm2022-23
2 1
Acm2022-23
2 2

Output

Acm2022-23
Acm2022-23-C0000

Note

After the first copying operation, we will have the following files.

• Acm2022-23
• Acm2022-23-C0000

After the second copying operation, we will have the following files.

• Acm2022-23
• Acm2022-23-C0000
• Acm2022-23-C0001
• Acm2022-23-C0000-C0000

after sorting the files lexicographically:

• Acm2022-23
• Acm2022-23-C0000
• Acm2022-23-C0000-C0000
• Acm2022-23-C0001

So, for the first test case, the answer will be the first file name after the second copying operation which is Acm2022-23.