A - Neq Number Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

正整数 X が以下の条件を満たすとき、X は “Neq Number” であるといいます。

  • X を十進法表記した際、どの隣接する 2 文字も相異なる

例えば 1,173,9090 は “Neq Number” です。一方、 22,6335 は “Neq Number” ではありません。

正整数 K が与えられます。小さいほうから K 番目の “Neq Number” を求めてください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1 \leq T \leq 100
  • 1 \leq K \leq 10^{12}
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

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

各ケースは以下の形式で与えられる。

K

出力

T 行出力せよ。i 行目には i 番目のテストケースに対する答えを出力せよ。

入力例 1

3
25
148
998244353

出力例 1

27
173
2506230721

1 つめのテストケースについて、 “Neq Number” を小さいものから 25 個あげていくと

  • 1 から 9 までの整数の 9 個
  • 10 から 19 までの整数のうち、 11 を除いた 9 個
  • 20 から 27 までの整数のうち、 22 を除いた 7 個

となります。よって、小さいほうから 25 番目の “Neq Number” は 27 となります。

Score: 400 points

Problem Statement

A positive integer X is called a "Neq Number" if it satisfies the following condition:

  • When X is written in decimal notation, no two adjacent characters are the same.

For example, 1, 173, and 9090 are Neq Numbers, while 22 and 6335 are not.

You are given a positive integer K. Find the K-th smallest Neq Number.

You have T test cases to solve.

Constraints

  • 1 \leq T \leq 100
  • 1 \leq K \leq 10^{12}
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Each case is given in the following format:

K

Output

Print T lines. The i-th line should contain the answer for the i-th test case.

Sample Input 1

3
25
148
998244353

Sample Output 1

27
173
2506230721

For the first test case, here are the smallest 25 Neq Numbers in ascending order:

  • The nine integers from 1 to 9
  • The nine integers from 10 to 19, excluding 11
  • The seven integers from 20 to 27, excluding 22

Thus, the 25-th smallest Neq Number is 27.