Description

当 Rar the Cat 前往台湾参加 IOI 2014 时，他住在一家酒店。在入住期间，他发现酒店大楼中有些楼层“消失”了。具体来说，他注意到包含 $4$ 和 $13$ 作为子串的数字在楼层编号中被省略了。这是因为 $4$ 和 $13$ 被认为是不吉利的数字，因此在编号时被有意跳过。

为简便起见，我们将这种编号方式称为“幸运编号方案”，因为它省略了不吉利的数字。下表展示了前 $20$ 层在幸运编号方案和常规编号方案下的对应关系。

:::align{center}

:::

然而，Rar the Cat 认为这种编号方式不够正规，他希望能够在幸运编号方案和常规编号方案之间进行楼层转换。例如，幸运编号方案下的第 $6$ 层对应常规编号方案下的第 $5$ 层，而幸运编号方案下的第 $15$ 层实际上是常规编号方案下的第 $12$ 层。因此，给定幸运编号方案下的某一楼层编号，Rar the Cat 希望你计算出它在常规编号方案下对应的楼层编号，反之亦然。

Input Format

你的程序需要从标准输入读取数据。

输入的第一行为一个整数 $N$，表示 Rar the Cat 需要你帮他转换的楼层编号的数量。

接下来的 $N$ 行，每行包含两个整数，分别为 $T_i$ 和 $X_i$。

如果 $T_i$ 为 $1$，你需要将 $X_i$ 从幸运编号方案转换为常规编号方案，并将结果输出在一行中。如果 $X_i$ 不是幸运编号方案下的有效楼层编号，则输出 $-1$。

如果 $T_i$ 为 $2$，你需要将 $X_i$ 从常规编号方案转换为幸运编号方案，并将结果输出在一行中。

保证答案不会超过 $64$ 位有符号整数。更多信息请参考样例测试 4 和 5。

Output Format

你的程序只需输出到标准输出。

共输出 $N$ 行，每行一个整数。对于每个 $i$，输出 $T_i$ 和 $X_i$ 的答案。

保证答案不会超过 $64$ 位有符号整数。

8
1 1
1 4
1 15
1 25
2 1
2 4
2 15
2 25

1
-1
12
21
1
5
18
29

10
1 1
2 4
1 15
2 15
1 26
1 131
2 131
2 1337
1 100000
2 100000

1
5
12
18
22
-1
178
1995
56160
190508

2
1 9
1 999999999999

8
245967827040

5
1 987328938823
1 75732858587173
1 4444444444444444
1 1313131313131313
1 10000000000000000

241928778399
13999321852875
-1
-1
1534593233484559

5
2 987328938823
2 75732858587173
2 4444444444444444
2 1313131313131313
2 10000000000000000

5110985302888
500859079673722
30071998020860537
8755153350232701
76732116285952928

Hint

样例解释

样例测试 1 仅适用于子任务 1、2、3、5 和 6。

样例测试 2 仅适用于子任务 2、3 和 6。

样例测试 3 仅适用于子任务 4、5 和 6。

样例测试 4 仅适用于子任务 5 和 6。

样例测试 5 仅适用于子任务 6。

子任务

每个测试点的最大运行时间为 $2.5$ 秒。你的程序将在满足以下限制的输入实例集上进行测试：

由 ChatGPT 4.1 翻译