Unlucky Floors

Time limit2.5sMemory limit512 MB

Summary

Convert floor numbers between a conventional scheme and one that skips any number containing the substrings 4 or 13, answering queries or reporting -1.

Level: Medium6 of 10
Topics: Math, Binary search, Implementation, Combinatorics
Solved: No attempts yet

Problem

When Rar the Cat went to Taiwan for IOI 2014, he stayed 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.

Conventional	Lucky
1	1
2	2
3	3
4	5
5	6
6	7
7	8
8	9
9	10
10	11
11	12
12	15
13	16
14	17
15	18
16	19
17	20
18	21
19	22
20	23

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.

Input

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

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.

Constraints

0 < N ≤ 100 000
Ti = 1 or 2
0 < Xi ≤ 10^16

Examples5

Example 1

Input

Expected output

Example 2

Input

Expected output

Example 3
Input
```
2
1 9
1 999999999999
```
Expected output
```
8
245967827040
```

Example 4

Input

5
1 987328938823
1 75732858587173
1 4444444444444444
1 1313131313131313
1 10000000000000000

Expected output

241928778399
13999321852875
-1
-1
1534593233484559

Example 5

Input

5
2 987328938823
2 75732858587173
2 4444444444444444
2 1313131313131313
2 10000000000000000

Expected output

5110985302888
500859079673722
30071998020860537
8755153350232701
76732116285952928

Conventional	Lucky
1	1
2	2
3	3
4	5
5	6
6	7
7	8
8	9
9	10
10	11
11	12
12	15
13	16
14	17
15	18
16	19
17	20
18	21
19	22
20	23

Conventional	Lucky
1	1
2	2
3	3
4	5
5	6
6	7
7	8
8	9
9	10
10	11
11	12
12	15
13	16
14	17
15	18
16	19
17	20
18	21
19	22
20	23

Conventional	Lucky
1	1
2	2
3	3
4	5
5	6
6	7
7	8
8	9
9	10
10	11
11	12
12	15
13	16
14	17
15	18
16	19
17	20
18	21
19	22
20	23