UnluckyFloors

When Rar the Cat went to Taiwan for IOI 2014, he was accomodated in a hotel. During his stay, he realised that certain floors are ‘missing’ from the hotel building. Namely, he observed that numbers containing 4 and 13 as substrings are omitted from the floor numberings. This is because 4 and 13 are considered unlucky numbers and are purposely left out in the numbering. For simplicity, we will refer to this numbering scheme as the lucky numbering scheme, as it omits the unlucky numbers. The table below shows the first 20 floors in a lucky numbering scheme as well as the conventional numbering scheme.

However, Rar the Cat feels that such a numbering scheme is not legitimate and wants to be able to convert floors between the lucky and conventional numbering scheme. For example, floor 6 in the lucky numbering scheme will be floor 5 in the conventional numbering scheme and floor 15 will actually be floor 12. Hence, given a floor number in the lucky numbering scheme, Rar the Cat wants you to compute which floor it will be in the conventional numbering scheme and vice-versa.

The input will start with a single integer, N, in a single line. N denotes how many floor numbers Rar the Cat wants you to convert for him.

N lines will then follow with 2 integers each, the i th line will contain Ti and Xi.

If Ti is 1, you are to convert Xi from the lucky numbering scheme to the conventional numbering scheme and print the result in a single line. However, if Xi is not a valid number in the lucky numbering scheme, print −1 as the answer instead

If Ti is 2, you are to convert Xi from the conventional numbering scheme to the lucky numbering scheme and print the result on a single line.

Output a total of N lines with 1 integer each. For each i, output the answer to Ti and Xi. It is guaranteed that the answer will fit in a 64-bit signed integer.

• 0 < N ≤ 100 000
• Ti = 1 or 2
• 0 < Xi ≤ 1016