Brunch Book

Good writing influences many people, and its value remains intact even when read again years later. "Brunch", operated by Kakao, is a service made for everyone who wants to write well.

Brunch lets you write, edit, and read on every device, so you can record ideas anytime, anywhere, and read beautifully anywhere. You can group the pieces you write by topic or together with other writers who share your interests into a "magazine" and serialize them. By carefully polishing the ideas laid out in a magazine into a "Brunch Book", you can create your own original work, and the Brunch team supports the process of that work being reborn as a book, a lecture, or a new derivative work.

Jongseo, a poet who captivates everyone with both strong programming skills and writing that moves the heart, decided to post his poems on Brunch in line with the latest trend. After reading the writing, Heewon thought it would be good for Jongseo to publish a poetry collection as a Brunch Book, and selected $T$ poems. While working on the Brunch Book, Jongseo felt that Heewon had chosen unexpected poems, so they talked it over and found that the title sorting method Heewon's environment used after downloading the poems differed from Jongseo's.

For example, suppose the $b$-th poem of the $a$-th book has a title of the form Book$a$Poem$b$. The $10$-th poem of the $2$-nd book gets the title Book2Poem10, and the $1$-st poem of the $10$-th book gets the title Book10Poem1. The ordinary string comparison used in programming, which Jongseo used, compares from the front and, when differing characters appear, decides the comparison by those characters. Here, at the $5$-th character, where the first difference appears, 2 is greater than 1, so Book2Poem10 is greater than Book10Poem1. But if you know that each poem belongs to the $2$-nd and $10$-th books, it would be natural to compare so that the poem of the $10$-th book is greater.

So Heewon sorted the book titles using the natural string comparison widely used elsewhere. In that string comparison, first all uppercase letters are changed to lowercase. Then consecutive digits are grouped and treated as a number for comparison. Scanning characters from the front, if both sides are digits, the numbers containing those digits are compared; otherwise the two characters are compared. For numbers starting with 0, if the two numbers have the same value, the string with more 0s is smaller. The following is an example of comparing titles using that string comparison: 005a $<$ 05ab $<$ 5abc $<$ 5bcd $<$ 006a $<$ 6abc $<$ 10ab $<$ abcd.

On day $X$, Jongseo wrote $16^X$ poems, and each poem's title used, without repetition, all $X$-character strings whose characters each come from 0123456789abcdef. Heewon said that among the $T$ poems, the $i$-th poem she liked was the $K_i$-th poem written on day $N_i$. What she meant was the $K_i$-th poem when all $16^{N_i}$ titles from day $N_i$ are sorted by natural string comparison, so there were cases where this pointed to a different book than the ordinary string comparison Jongseo used in programming. Jongseo would normally have written a program himself to find the poem titles, but since he wanted to finish the Brunch Book quickly, he asked you to tell him the title of each poem Heewon selected.

The input is given as follows.

$T$

$N_1$ $K_1$

$\dots$

$N_T$ $K_T$

• $T$ is the number of poems Heewon selected. ($1 \le T \le 1\,000$)
• $N_i$ and $K_i$ describe the poem Heewon selected. They mean that the $i$-th selected poem is the $K_i$-th poem when all $16^{N_i}$ poems from day $N_i$ are sorted by natural string comparison. ($1 \le N_i \le 15$, $1 \le K_i \le 16^{N_i}$)
• All numbers in the input are integers.

Output $N$ lines in total. On the $i$-th line, output the title of the $i$-th poem Heewon selected.