Miruna tocmai s-a angajat intr-o
firmă în care există 2N - 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 2N - 1 angajaţi au
numere unice de identificare de la 1 la 2N - 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.
Cei 2N - 1 angajaţi au
numere unice de identificare de la 1 la 2N - 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 A1 şi B1 - valorile pentru primul test. Pentru toate celelalte teste va veţi folosi de următoarea recurenţă: Ai = (Ai-1 * i) % 1000003 şi Bi = (Bi-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 <= 106
- 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 <= 105
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 |