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}