問題文

正整数 $K$ が与えられます。 以下の条件をすべて満たす最小の正整数 $n$ を求めてください。存在しないなら -1 を出力してください。

• $n$ の桁和は $K$ である。
• $10^x\leq n< 10^{x+1}$ を満たす唯一の整数を $x$、$n$ を十進数として解釈したときの $10^i$ の位の値を $n_i$ と定義したとき、任意の $0\leq i\leq x-2$ を満たす非負整数 $i$ について $n_{i+2} \gt n_{i+1} + n_i$ が成り立つ。

ここで、$n< 100$ である時は常に2つ目の条件を満たすことに注意してください。

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

制約

• 入力される値はすべて整数
• $1 \leq T \leq 1000$
• $1 \leq K \leq 10^6$
• すべてのテストケースにわたる $K$ の総和は $10^6$ 以下

入力

$T$
$Test_1$
$Test_2$
$\vdots$
$Test_T$

$K$

出力

$T$ 行出力してください。

$i$ 行目には $i$ 個目のテストケースの答えを出力してください。

サンプル

2
16
9231

79
-1