当猫咪 Rar 在 2014 年去台湾参加 IOI 时，他入住了一家酒店。在住宿期间，他发现酒店大楼中“缺失”了某些楼层。具体来说，他注意到所有包含 4 和 13 作为子串的数字都在楼层编号中被省略了。这是因为 4 和 13 被认为是不吉利的数字，因此在编号中被刻意避开。为了简单起见，我们将这种省略了不吉利数字的编号方案称为幸运编号方案（lucky numbering scheme）。下表展示了幸运编号方案与传统编号方案（conventional numbering scheme）的前 20 个楼层对照：
| 传统编号 | 幸运编号 |
|---|---|
| 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 |
然而，猫咪 Rar 觉得这样的编号方案并不合理，并希望能够在幸运编号方案和传统编号方案之间进行楼层转换。例如，幸运编号方案中的第 6 层在传统编号方案中实际上是第 5 层，而幸运编号方案中的第 15 层实际上是第 12 层。因此，给定一个幸运编号方案中的楼层号，猫咪 Rar 希望你计算出它在传统编号方案中对应的楼层号，反之亦然。
输入格式
您的程序必须从标准输入中读取。
输入的第一行包含一个整数 $N$，表示猫咪 Rar 需要您帮他转换的楼层数量。
接下来的 $N$ 行，每行包含两个整数，其中第 $i$ 行包含 $T_i$ 和 $X_i$。
如果 $T_i$ 为 $1$，您需要将 $X_i$ 从幸运编号方案转换为传统编号方案，并在单行中输出结果。然而，如果 $X_i$ 在幸运编号方案中不是一个合法的楼层号，则输出 -1 作为答案。
如果 $T_i$ 为 $2$，您需要将 $X_i$ 从传统编号方案转换为幸运编号方案，并在单行中输出结果。
输出格式
您的程序必须仅输出到标准输出。
共输出 $N$ 行，每行包含一个整数。对于每个 $i$，输出对应 $T_i$ 和 $X_i$ 的答案。
保证答案可以表示为一个 64 位有符号整数。有关更多信息，请参考样例 4 和样例 5。
子任务
在每个测试点上，最大运行时间限制为 2.5 秒。您的程序将在满足以下限制的输入实例集上进行测试：
| 子任务 | 分值 | $N$ | $T_i$ | $X_i$ |
|---|---|---|---|---|
| 1 | 5 | $0 < N \le 50$ | $T_i = 1$ 或 $2$ | $0 < X_i \le 25$ |
| 2 | 12 | $0 < N \le 50$ | $T_i = 1$ 或 $2$ | $0 < X_i \le 100\,000$ |
| 3 | 18 | $0 < N \le 100\,000$ | $T_i = 1$ 或 $2$ | $0 < X_i \le 100\,000$ |
| 4 | 11 | $0 < N \le 100\,000$ | $T_i = 1$ | $X_i = 10^K - 1$，其中 $1 \le K \le 16$ |
| 5 | 37 | $0 < N \le 100\,000$ | $T_i = 1$ | $0 < X_i \le 10^{16}$ |
| 6 | 17 | $0 < N \le 100\,000$ | $T_i = 1$ 或 $2$ | $0 < X_i \le 10^{16}$ |
样例
输入样例 1
8 1 1 1 4 1 15 1 25 2 1 2 4 2 15 2 25
输出样例 1
1 -1 12 21 1 5 18 29
说明 1
此样例仅对子任务 1, 2, 3, 5 和 6 有效。
输入样例 2
10 1 1 2 4 1 15 2 15 1 26 1 131 2 131 2 1337 1 100000 2 100000
输出样例 2
1 5 12 18 22 -1 178 1995 56160 190508
说明 2
此样例仅对子任务 2, 3 和 6 有效。
输入样例 3
2 1 9 1 999999999999
输出样例 3
8 245967827040
说明 3
此样例仅对子任务 4, 5 和 6 有效。
输入样例 4
5 1 987328938823 1 75732858587173 1 4444444444444444 1 1313131313131313 1 10000000000000000
输出样例 4
241928778399 13999321852875 -1 -1 1534593233484559
说明 4
此样例仅对子任务 5 和 6 有效。
输入样例 5
5 2 987328938823 2 75732858587173 2 4444444444444444 2 1313131313131313 2 10000000000000000
输出样例 5
5110985302888 500859079673722 30071998020860537 8755153350232701 76732116285952928
说明 5
此样例仅对子任务 6 有效。