Merkitään $f(n)$:llä pienintä askelten määrää prosessissa, jossa aloitetaan luvusta $n$ ja joka askeleella valitaan jokin luvun numeroista ja vähennetään se luvusta, kunnes päästään lukuun $0$.

Esimerkiksi $f(15)=3$, koska optimaalinen ratkaisu on $15 \rightarrow 10 \rightarrow 9 \rightarrow 0$.

Kun annettuna on positiivinen kokonaisluku $x$, tehtäväsi on etsiä pienin positiivinen kokonaisluku $k$, jolle pätee $f(k)=x$.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku $t$: testien määrä.

Tämän jälkeen tulee $t$ riviä, joista jokaisella on yksi kokonaisluku $x$: haluttu askelten määrä.

Tuloste

Tulosta jokaisesta testistä pienin kokonaisluku $k$, jolle pätee $f(k)=x$. Jos tällaista lukua ei ole, tulosta sen sijasta $-1$.

Esimerkki

Syöte:

5
1
2
3
4
5

Tuloste:

1
10
11
20
22

Osatehtävä 1 (12 pistettä)

• $1 \le t \le 1000$
• $1 \le x \le 1000$

Osatehtävä 2 (13 pistettä)

• $1 \le t \le 1000$
• $1 \le x \le 10^6$

Osatehtävä 3 (75 pistettä)

• $1 \le t \le 1000$
• $1 \le x \le 10^{18}$