Piirissä on n lasta, jotka on numeroitu myötäpäivään 1,2,\dots,n. Leikissä vuoro kiertää piirissä järjestyksessä alkaen lapsesta 1. Joka toinen lapsi jää piiriin ja joka toinen lapsi lähtee pois piiristä. Näin jatkuu, kunnes piirissä on enää yksi lapsi, joka lähtee viimeisenä.

Yllä oleva kuva vastaa tilannetta, jossa n=7. Tässä tapauksessa lapset lähtevät piiristä järjestyksessä 2,4,6,1,5,3,7.

Tehtäväsi on selvittää pienin n, jolla lapset a ja b lähtevät piiristä peräkkäin niin, että lapsi b lähtee heti lapsen a jälkeen.

Syöte

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

Tämän jälkeen tulee t riviä, joista jokaisella on kaksi kokonaislukua a ja b.

Tuloste

Tulosta jokaiseen testiin pienin n. Jos ratkaisua ei ole olemassa, tulosta -1.

Esimerkki

Syöte:

10
1 3
2 1
2 2
2 3
2 4
2 5
3 1
3 7
42 44
1337 17

Tuloste:

3
2
-1
-1
4
-1
4
7
44
1344

Osatehtävä 1 (5 pistettä)

• 1 \le t \le 1000
• 1 \le a, b \le 100

Osatehtävä 2 (8 pistettä)

• 1 \le t \le 1000
• 1 \le a, b \le 1000

Osatehtävä 3 (10 pistettä)

• 1 \le t \le 1000
• 1 \le a, b \le 10^6
• a on parillinen

Osatehtävä 4 (29 pistettä)

• 1 \le t \le 1000
• 1 \le a, b \le 10^6
• a<b

Osatehtävä 5 (37 pistettä)

• 1 \le t \le 1000
• 1 \le a, b \le 10^6

Osatehtävä 6 (11 pistettä)

• 1 \le t \le 10^5
• 1 \le a, b \le 10^6