Lukujonon alkuarvona on positiivinen kokonaisluku x. Lukujono muodostetaan seuraavien sääntöjen perusteella:

1. Jos luku on jaollinen 3:lla, se jaetaan 3:lla.
2. Jos luku ei ole jaollinen 3:lla, se kerrotaan 2:lla ja lisätään 1.
3. Jos luku on 1, lukujono päättyy.

Esimerkiksi kun alkuarvo on x=12, lukujono on 12 \rightarrow 4 \rightarrow 9 \rightarrow 3 \rightarrow 1.

Tehtäväsi on laskea lukujonon pituus alkuarvolle x tai todeta, että lukujono jatkuu ikuisesti.

Syöte

Ensimmäisellä rivillä on kokonaisluku t: testien määrä.

Seuraavaksi tulee t riviä, joista jokaisella on kokonaisluku x: lukujonon alkuarvo.

Tuloste

Tulosta jokaisessa testissä lukujonon pituus tai -1, jos lukujono jatkuu ikuisesti.

Esimerkki

Syöte:

5
1
2
3
4
12

Tuloste:

1
-1
2
4
5

Arvostelu

Jokaisessa testissä 1 \le t \le 1000 ja 1 \le x \le 10^6. Saat tehtävästä 100 pistettä, jos koodisi tuottaa oikean tuloksen kaikissa testeissä.