Wesoła małpka
Limit pamięci: 64 MB
Wesoła małpka znalazła sobie nową zabawę. Ustawiła klatek ze zwierzątkami
(w jednej klatce jest dokładnie jedno zwierzątko) w kółeczko i skacze po nich.
Małpka zawsze skacze o kolejnych klatek i zawsze otwiera tę, na której stoi.
Małpka zatrzyma się, gdy skoczy na wcześniej otwartą klatkę.
Twoim zadaniem jest stwierdzić, ile zwierzątek ucieknie. Wiadomo, że wszystkie
klatki są początkowo zamknięte oraz każde zwierzątko (poza wesołą małpką)
korzysta z okazji i ucieka jeśli może.
Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą (),
oznaczającą liczbę zestawów danych. W następnych wierszach opisywane są kolejne zestawy danych.
Każdy wiersz zawiera po dwie liczby całkowite i (),
oznaczające odpowiednio liczbę klatek oraz długość skoku małpki (, oznacza,
że małpka przeskoczy na następną w kolejności klatkę).
W testach wartych co najmniej punktów
zachodzą dodatkowe warunki: .
Wyjście
Dla każdego zestawu danych powinna się znaleźć w nowym wierszu jedna liczba całkowita, równa
liczbie zwierzątek, które uciekną.
Przykład
Dla danych wejściowych:
2
3 1
3 2
poprawną odpowiedzią jest:
3
3
Autor zadania: Joanna Bujnowska.