Never Be Nabeatsu

問題文

数学者のsandさんとmoguさんがとあるゲームで遊んでいる。ゲームのルールは次の通り。

• 任意の正整数 $X$ を用意してゲームを始める。最初、変数 $X$ の値は $a$ であり、 $3$ の倍数でなく、10進法での表記に $3$ を含むことはない。先攻のsandさんから順番に次の操作を行う。
• (操作) $1 \leq i \leq K$ を満たすような任意の整数 $i$ を選び、$X$ に $i$ を加算する。ただし、$X$ が $3$ の倍数になったり、$X$ の10進法での表記に $3$ を含んだりしてはならない。

先に操作が出来なくなったほうの負けである。また、相手を負けにしたほうがゲームに勝つ。二人が最善を尽くした際、moguさんが必ず勝つことができるような $K$ 以下の $a$ の値を求めよ。 $T$ 個のテストケースが与えられるので、それぞれのテストケースについて答えること。

制約

• $1 \leq T \leq 10^4$
• $1 \leq K \leq 3 \times 10^{10}$
• 各テストケースについて、答えは一意に定まる。

入力

入力はすべて整数である。

T
K_1
K_2
...
K_3

出力

各テストケースについて、条件を満たす $a$ の値をテストケースごとに出力せよ。そのような $a$ が存在しない場合は -1 を出力せよ。

サンプル

1
2

2

例えば、次のようにゲームが進行します。sandさんの番の状態を$S$,moguさんの番の状態を$M$で表現します。

$S2 \rightarrow M4 \rightarrow S5 \rightarrow M7$ $\rightarrow S8 \rightarrow M10 \rightarrow S11$

1
1

-1

$X = 1$ のときsandさんが必ず勝ちます。よって $K$ 以下の $a$ でmoguさんが勝つことは不可能なので、 $-1$ を出力します。