FRAKTAL - konkurs programistyczny

Po raz kolejny uruchamiasz swoją ulubioną grę: World of Bajtcraft. Jako wytrawny gracz postanawiasz spróbować wygrać w najtrudniejszy możliwy sposób - poprzez zwycięstwo kulturalne. Polega ono na tym, że wygrywa gracz, który jako pierwszy zbuduje jeden z cudów świata.

Nie jest to jednak takie proste. Trzeba najpierw uzbierać ogromną ilość surowców. Zakładając, że skupiasz się tylko i wyłącznie na zbieraniu surowców, policz w jakim czasie jesteś w stanie uzbierać potrzebne materiały (oczywiście chcesz to zrobić jak najszybciej).

Na początku gry masz do dyspozycji jednego robotnika. Robotnik pracuje w kopalni i co minutę przynosi k surowców. Możesz wyprodukować nowego robotnika, ale to będzie kosztowało s surowców i trwało m minut (żeby rozpocząć produkcje nowego robotnika musisz mieć w banku dostępne wymagane surowce). Możesz produkować tylko jednego robotnika w danym momencie (nawet jak masz zasoby na kupno kilku na raz). Twój cel, to jak najszybsze uzbieranie g surowców.

Celem jest posiadanie w banku g surowców. Nie mówimy tutaj o sumarycznej liczbie surowców, jakie uzbieraliśmy przez cały czas trwania rozgrywki.

Wejście

Na wejściu znajduje się t - liczba testów (t ≤ 2000)

Każdy test składa się z 4 wartości: k, s, m, g (0 < k, s, m, g ≤ 10⁵) opisanych w treści zadania.

Wyjście

Ile co najmniej minut potrzeba na uzbieranie wymaganych surowców.

Przykład

Wejście:

3
2 3 4 10
2 3 4 20
1 1 1 100000

Wyjście:

5
9
449