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.