Liga baseballowa KOI składa się z $N$ lig regionalnych,

a każda ma $M$ drużyn, więc cała liga liczy $N \times M$ drużyn.

W sezonie każda drużyna musi grać zarówno z drużynami swojej ligi regionalnej, jak i z drużynami innych lig regionalnych.

Liczba meczów z każdą drużyną tej samej ligi regionalnej wynosi $A$ i jest jednakowa dla wszystkich takich przeciwników.

Zatem drużyna $X$ rozgrywa po $A$ meczów z każdą drużyną $Y$ ($Y \ne X$) swojej ligi regionalnej.

Liczba meczów z każdą drużyną innych lig regionalnych wynosi $B$ i jest jednakowa dla wszystkich takich przeciwników.

Zatem drużyna $X$ rozgrywa po $B$ meczów z każdą drużyną $Z$ ($Z \ne X$) innych lig regionalnych.

Liczby $A$ i $B$ muszą spełniać $A = k \times B$, gdzie $k$ jest liczbą całkowitą co najmniej $1$.

Z powodu światowej pandemii liga KOI postanowiła w tym roku skrócić sezon,

wybierając łączną liczbę meczów nie większą niż $D$ i możliwie najbliższą $D$.

Trzeba więc na nowo ustalić liczby $A$ i $B$ meczów z każdą drużyną tej samej i innych lig regionalnych.

Oczywiście nadal musi zachodzić $A = k \times B$, a $k$ musi pozostać bez zmian.

Ponadto każda drużyna musi zagrać z każdą inną co najmniej raz.

Innymi słowy, musi zachodzić $A \ge 1$ i $B \ge 1$.

Na przykład dla $N = 2$, $M = 3$, $k = 3$ i limitu $D = 60$, wybór $A = 6$, $B = 2$ daje

łącznie $18$ meczów między drużynami różnych lig regionalnych i $36$ między drużynami tej samej ligi regionalnej.

Łącznie liga rozegra więc $54$ mecze; jest to nowa liczba najbliższa $D$.

Dane są liczba lig regionalnych $N$, liczba drużyn w każdej z nich $M$,

liczba całkowita $k$ spełniająca $A = k \times B$ oraz nowy limit meczów $D$.

Napisz program obliczający i wypisujący łączną liczbę meczów ligi, która jest nie większa niż $D$ i najbliższa $D$.

[Ograniczenia]

* Wszystkie podane liczby są całkowite.

* Każde wejście zawiera od $1$ do $1,000$ przypadków testowych do rozwiązania.

* $2 \le N, M \le 100$

* $1 \le k \le 100$

* $1 \le D \le 1,000,000,000$

Wejście

Pierwszy wiersz zawiera liczbę przypadków testowych $T$.

Każdy z następnych $T$ wierszy zawiera informacje o jednym przypadku testowym.

Każdy przypadek składa się z czterech liczb całkowitych $N$, $M$, $k$, $D$ w jednym wierszu, oddzielonych pojedynczymi spacjami.

Wyjście

Dla każdego przypadku wypisz łączną liczbę meczów ligi w osobnym wierszu, łącznie w $T$ wierszach.

Jeśli nie istnieje liczba meczów spełniająca warunki, wypisz $-1$.

Podzadania

1. ($5$ pkt) $N = 2$
2. ($5$ pkt) $M = 2$
3. ($5$ pkt) $k = 1$
4. ($85$ pkt) Brak dodatkowych ograniczeń.

Przykład

Wejście 1

3
2 3 3 60
2 2 1 18
2 2 1 4

Wyjście 1

54
18
-1