Annettuna on kaksi pinoa, joissa on kolikoita. Joka siirrolla poistat suuremmasta pinosta niin monta kolikkoa kuin on pienemmässä pinossa. Monenko siirron jälkeen toinen pino on tyhjä?

Esimerkiksi jos pinoissa on alussa 3 ja 10 kolikkoa, siirtoja tulee 6: (3,10) \rightarrow (3,7) \rightarrow (3,4) \rightarrow (3,1) \rightarrow (2,1) \rightarrow (1,1) \rightarrow (0,1) Huomaa, että jos pinoissa on sama määrä kolikoita, ei ole merkitystä, kummin päin valinta tehdään.

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: kolikoiden määrä pinoissa.

Tuloste

Tulosta t riviä: jokaisesta testistä siirtojen määrä.

Esimerkki

Syöte:

3
3 10
5 5
1 100

Tuloste:

6
1
100

Osatehtävä 1 (23 pistettä)

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

Osatehtävä 2 (77 pistettä)

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