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$