Problem description

Back
Show PDF
Rajdowiec
(H)
Limit pamięci: 512 MB
Limit czasu: 1.00 s

Rajdowiec startuje z nowymi oponami o początkowej wytrzymałości k. Przejeżdża kolejne okrążenia w następujący sposób:

  1. Dopóki aktualna wytrzymałość opon d jest dodatnia (d > 0):
    • Przejeżdża d okrążeń.
    • Po przejechaniu tych okrążeń wytrzymałość opon zmniejsza się o wartość m: d ← d − m.
  2. Gdy d ≤ 0, rajdowiec przestaje jeździć.

Chcemy obliczyć, ile okrążeń w sumie przejedzie rajdowiec, zanim wytrzymałość opon spadnie do zera lub poniżej.

Wejście

W pierwszej linii znajduje się liczba całkowita q — liczba zapytań. W każdej z kolejnych q linii dwie liczby całkowite ki oraz mi.

Wyjście

Dla każdego zapytania wypisz w osobnej linii łączną liczbę okrążeń, które rajdowiec przejedzie, zanim wytrzymałość opon stanie się mniejsza lub równa zero.

Ograniczenia

  • 1 ≤ q ≤ 1 000
  • 1 ≤ ki, mi ≤ 109

Przykład

Wejście Wyjście Wyjaśnienie 
3
10 3
5 2
7 7

22
9
7

Dla k = 10, m = 3 kolejność wytrzymałości: 10 → 7 → 4 → 1 → -2, suma okrążeń 10 + 7 + 4 + 1 = 22. Dla k = 5, m = 2: 5 → 3 → 1 → -1, suma 5 + 3 + 1 = 9. Dla k = 7, m = 7: 7 → 0, suma 7.