0469 - 門松ナンバー

もんだいー

門松列 とは 3 個の要素からなる数列 A₁,A₂,A₃ 以下の 2 つの条件を満たすものです。

・ A₁,A₂,A₃ は全て異なる
・ 3 つの要素の中で A₂ が最も大きい、または、A₂ が最も小さい

N桁 (3≤N) の 正整数X の上から i桁目 の数を X_i とします。
数列 X_i, X_i+1, X_i+2 (1≤i≤N−2 ) が全て門松列になるとき、Xは門松ナンバーです。
例えば、 4514 や 893 は門松ナンバーですが、 114514 や 89 は門松ナンバーではありません。

X が門松ナンバーであり、X より小さい門松ナンバーが K個 存在するとき、X は K+1番目 の門松ナンバーであるといいます。
1番目の門松ナンバーは102、404番目の門松ナンバーは893、1000番目の門松ナンバーは3296です。

正整数K(1≤K≤10^10) が与えられるので、 K番目の門松ナンバーを求めてください。

入力

1 行目にテストケース数 T (1≤T≤10)（整数）が与えられる。

T

以降T行に、各テストケースのK （整数）が与えられる。

K

出力

各テストケース毎1行に、K番目の門松ナンバーを出力してください。

---

入出力例

入力例1

5
1
2
3
4
5

出力例1

102
103
104
105
106

注意

1桁、2桁の門松ナンバーは存在しないことに注意してください。

入力例2

4
114
215
404
1000

出力例2

328
514
893
3296

入力例2

1
10000000000

出力例2

37294859064823

注意

最大のケースです。 10^10 は 32bit整数型に収まりません。 計算時だけでなく入出力時のオーバーフローにも注意しましょう。