题目描述

当且仅当正整数 $X$ 满足以下条件时，称 $X$ 为 “Neq Number”。

• 将 $X$ 用十进制表示时，任意相邻的两个数字都不相同。

例如，$1$、$173$、$9090$ 都是 “Neq Number”。而 $22$、$6335$ 则不是 “Neq Number”。

给定正整数 $K$，请你求出从小到大第 $K$ 个 “Neq Number”。

有 $T$ 组测试数据，请分别输出每组的答案。

输入格式

输入按以下格式从标准输入读入。

$T$
$\mathrm{case}_1$
$\vdots$
$\mathrm{case}_T$

每组数据为一行，包含一个整数 $K$。

输出格式

输出 $T$ 行。第 $i$ 行输出第 $i$ 组测试数据的答案。

样例 1

输入

3
25
148
998244353

输出

27
173
2506230721

说明/提示

限制

• $1 \leq T \leq 100$
• $1 \leq K \leq 10^{12}$
• 所有输入均为整数。

样例解释 1

对于第 $1$ 组测试数据，从小到大列出前 $25$ 个 “Neq Number” 如下：

• $1$ 到 $9$ 共 $9$ 个。
• $10$ 到 $19$，去掉 $11$，共 $9$ 个。
• $20$ 到 $27$，去掉 $22$，共 $7$ 个。

因此，从小到大第 $25$ 个 “Neq Number” 是 $27$。

由 ChatGPT 4.1 翻译