001 - 門松ナンバー

時間制限 1 秒 / メモリ制限 64 MB / 得点 1 / x 0 /


TLE
1sec
MLE
64MB
得点
1

もんだいー

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

・ A1,A2,A3 は全て異なる
・ 3 つの要素の中で A2 が最も大きい、または、A2 が最も小さい

N桁 (3≤N) の 正整数X の上から i桁目 の数を Xi とします。
数列 Xi, Xi+1, Xi+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整数型に収まりません。 計算時だけでなく入出力時のオーバーフローにも注意しましょう。