CF1811E Living Sequence

在日本，数字 $4$ 的发音与“死”相似，因此 Bob 决定构造一个“生命序列”。生命序列 $a$ 包含所有不含数字 $4$ 的自然数。$a = [1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, \ldots]$。 例如，数字 $1235$ 属于序列 $a$，但数字 $4321$、$443$ 不属于序列 $a$。 Bob 发现他不知道如何快速地根据位置 $k$ 查找序列中的特定数字，因此他请求你的帮助。 例如，如果 Bob 想找到第 $k = 4$ 个数字（从 $1$ 开始计数），你需要回答 $a_k = 5$。

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的唯一一行包含一个整数 $k$（$1 \le k \le 10^{12}$），表示 Bob 感兴趣的位置。

对于每个测试用例，输出一行，表示序列 $a$ 中第 $k$ 个数字（从 $1$ 开始计数）。

由 ChatGPT 4.1 翻译