Bogdan si Ștefan joaca M runde ale unui joc. La runda i, se foloseste o hartie cu N celule patratice asezate in linie dreapta, iar pe una din celule se afla un paianjen, pe pozitia P (celulele fiind numerotate de la 1 la N).
Bogdan incepe intotdeauna primul fiecare runda. Pe rand, jucatorul aflat la mutare taie hartia in doua bucati, dupa latura unei celule, iar bucata ce contine paianjenul este pasata celuilalt jucator (bucata fara paianjen este aruncata). Jucatorul care nu mai poate taia (adica ramane cu o singura celula, cea a paianjenului, in mana) pierde runda.
Ambii jucatori joaca optim. Cerinta: determinati cate din cele M runde le castiga Bogdan.
- Date de intrare
- Pe prima linie: M. Urmeaza M linii, fiecare continand cate doua numere N si P (dimensiunea hartiei, respectiv pozitia paianjenului).
- Date de iesire
- Se afiseaza numarul de runde castigate de Bogdan.
- Restrictii
- 1 <= M <= 1000 2 <= N <= 1000000000 1 <= P <= N
Exemple
Exemplul 1
Intrare
6 3 2 4 2 5 2 6 3 7 3 8 4
Iesire
5
Exemplul 2
Intrare
1 5 3
Iesire
0