Problem description

Algosia gra z rodzicami w grę planszową. Plansza składa się z N pól ponumerowanych kolejno 1, 2, …, N. Pionek Algosi początkowo stoi na polu nr 1. Celem gry jest dotrzeć swoim pionkiem do ostatniego, N-tego pola. W każdej turze Algosia rzuca K-ścienną kością i przesuwa się o liczbę wylosowanych pól. Algosia zaczęła zastanawiać się, ile co najmniej rzutów kością musi wykonać, żeby dotrzeć do końca planszy?

Wejście

W pierwszym wierszu znajduje się jedna liczba naturalna T opisująca liczbę zestawów testowych. W następnych T wierszach znajduje się opis kolejnych zestawów testowych. Każdy opis składa się z dwóch liczb całkowitych N, K, oznaczających odpowiednio długość planszy oraz rozmiar kości.

Wyjście

Dla każdego zestawu testowego należy wypisać jedną liczbę całkowitą, oznaczającą minimalną liczbę rzutów kością konieczną do dotarcia do ostatniego pola planszy.

Ograniczenia

1 ≤ T ≤ 1 000, 1 ≤ N, K ≤ 10⁹.

Przykład

3
17 5
5 1
6 14

4
4
1