Miruna tocmai s-a angajat intr-o firmă în care există 2^N - 1 angajaţi. Aceştia sunt organizaţi pe N niveluri ierarhice, astfel: pe primul nivel ierarhic există un manager principal, care are exact doi subalterni direcţi, aceştia aflându-se pe al doilea nivel ierarhic. Cei doi subalterni au şi ei câte doi suboronaţi direcţi, care se află pe cel de-al treilea nivel ierarhic. Toţi ceilalţi angajaţi au la rândul lor câte doi subordonaţi, mai puţin cei de pe ultimul nivel ierarhic, care nu sunt şefii nimănui.

Cei 2^N - 1 angajaţi au numere unice de identificare de la 1 la 2^N - 1. Un lucru foarte interesant pe care l-a observat Miruna este urmatoarea regulă: pentru un anumit angajat cu numărul de identificare X, unul din cei doi subalterni direcţi are numărul de identificare mai mic decât X, iar celălalt subaltern mai mare decât X. Deasemena, subordonaţii direcţi ai subalternului cu numărul de identificare mai mic decât X, au la rândul lor numere de identificare mai mici decât X. Subordonaţii direcţi ai celuilalt subaltern au numere de identificare mai mari decât X. Acelaşi raţionament se aplică în continuare, până la angajaţii de pe ultimul nivel ierarhic. Pentru mai multe detalii despre organizarea internă a firmei puteţi consulta imaginea alăturată.

De curând, un anumit angajat cu numărul de identificare A a aflat o bârfă importantă despre Miruna. El vrea sa îi spună această bârfă angajatului cu numărul de identificare B. Din păcate, un anumit angajat nu poate să comunice decât cu şeful direct, sau cu subordonaţii direcţi. Pentru a transmite bârfa este necesar exact un minut.

Cerinţă

Ştiind că traseul de transmitere a bârfei este minim şi că un angajat transmite bârfa mai departe imediat cum o află, se cere sa determinaţi câte minute trec până când angajatul cu numărul de identificare B aude la rândul său veştile.

Date de intrare

Fişierul de intrare barfa.in conţine pe prima linie un număr natural T reprezentând numărul de teste ce vor urma. Urmatoarea linie contine două numere naturale A₁ şi B₁ - valorile pentru primul test. Pentru toate celelalte teste va veţi folosi de următoarea recurenţă: A_i = (A_i-1 * i) % 1000003 şi B_i = (B_i-1 * i) % 1000003 (veţi avea nevoie de numere întregi pe 64 de biţi pentru recurenţă).

Date de ieşire

Fişierul de ieşire barfa.out va conţine T linii, pe ficare linie aflându-se un număr natural reprezentând numărul de minute necesar pentru transmiterea bârfei pentru fiecare test in parte.

Restricţii şi precizări

• 1 <= T <= 10⁶
• 1 <= A, B < 1000003
• Numărul total de angajaţi este destul de mare încât să existe angajaţii cu numerele de ordine A şi B
• Pentru 70% din teste 1 <= T <= 10⁵

Exemple

barfa.in	barfa.out
5 1 2	1 1 3 3 7

Andrei Grigorean

Facultatea de Matematică şi Informatică, Universitatea din Bucureşti

andrei.grigorean@gmail.com