Turniej
Limit pamięci: 128 MB
W Bajtockim Turnieju Programistycznym bierze udział zawodników. Każdy zawodnik ma pewną siłę i wiadomo, że dwóch różnych zawodników nie posiada takiej samej siły.
Codziennie odbywane są zawody z udziałem zawodników, którzy zakwalifikowali się z dnia poprzedniego. W jednym dniu zawodnicy dzieleni są losowo na pewną liczbę grup po osób, spośród których odpada zawsze osoba z najmniejszą siłą (pozostałych osób zostaje zwycięzcami w danej grupie). Może się zdarzyć, że jedna grupa nie będzie posiadała osób. W tym wypadku wszystkie osoby z danej grupy
przechodzą automatycznie do zawodów następnego dnia. Turniej się kończy, jeśli nie można już podzielić osób na co najmniej jedną grupę o liczbie osób . W całym turnieju szukamy więc zwycięzców.
Zastanawiamy się, ile różnych osób może zwyciężyć w tym turnieju.
Wejście
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę zestawów danych. Każdy zestaw danych zawiera po dwie liczby całkowite i (), oznaczające odpowiednio liczbę osób biorących udział w turnieju oraz liczbę osób, na które dzielone są grupy.
Wyjście
Dla każdego zapytania w osobnym wierszu powinna znaleźć się jedna liczba całkowita oznaczająca liczbę różnych osób, które mogą być zwycięzcami w całym turnieju.
Przykład
Dla danych wejściowych:
3
4 2
3 3
5 3
poprawną odpowiedzią jest:
1
2
2
Autor zadania: Jacek Tomasiewicz.