Die KOI-Baseballliga besteht aus $N$ Regionalligen,

die jeweils $M$ Mannschaften haben. Insgesamt gibt es also $N \times M$ Mannschaften.

In einer Saison muss jede Mannschaft sowohl gegen Mannschaften ihrer eigenen als auch anderer Regionalligen spielen.

Die Anzahl der Spiele gegen jede Mannschaft derselben Regionalliga beträgt $A$ und ist für all diese Gegner gleich.

Das heißt, eine Mannschaft $X$ spielt jeweils $A$ Spiele gegen jede Mannschaft $Y$ ($Y \ne X$) derselben Regionalliga.

Die Anzahl der Spiele gegen jede Mannschaft anderer Regionalligen beträgt $B$ und ist für all diese Gegner gleich.

Das heißt, eine Mannschaft $X$ spielt jeweils $B$ Spiele gegen jede Mannschaft $Z$ ($Z \ne X$) anderer Regionalligen.

Dabei muss $A = k \times B$ gelten, wobei $k$ eine ganze Zahl mindestens $1$ ist.

Wegen einer weltweiten Pandemie soll die diesjährige KOI-Baseballsaison verkürzt werden,

sodass die Gesamtzahl der Spiele höchstens $D$ und möglichst nahe an $D$ ist.

Daher müssen die Spielzahlen $A$ und $B$ gegen jede Mannschaft derselben beziehungsweise anderer Regionalligen neu festgelegt werden.

Natürlich muss weiterhin $A = k \times B$ gelten, und $k$ muss unverändert bleiben.

Außerdem muss jede Mannschaft gegen jede andere mindestens einmal spielen.

Mit anderen Worten muss $A \ge 1$ und $B \ge 1$ gelten.

Für $N = 2$, $M = 3$, $k = 3$ und das Limit $D = 60$ ergibt beispielsweise die Wahl $A = 6$, $B = 2$

insgesamt $18$ Spiele zwischen Mannschaften verschiedener Regionalligen und $36$ innerhalb derselben Regionalliga.

Die Liga hat damit insgesamt $54$ Spiele, die neue Gesamtzahl am nächsten an $D$.

Gegeben sind die Anzahl der Regionalligen $N$, die Anzahl der Mannschaften pro Regionalliga $M$,

die ganze Zahl $k$ mit $A = k \times B$ und das neue Spiellimit $D$.

Schreibe ein Programm, das die Gesamtzahl der Spiele berechnet und ausgibt, die höchstens $D$ und möglichst nahe an $D$ ist.

[Beschränkungen]

* Alle gegebenen Zahlen sind ganzzahlig.

* Jede Eingabe enthält mindestens $1$ und höchstens $1,000$ zu lösende Testfälle.

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

* $1 \le k \le 100$

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

Eingabe

Die erste Zeile enthält die Anzahl der Testfälle $T$.

Jede der folgenden $T$ Zeilen enthält die Informationen für einen Testfall.

Ein Testfall besteht aus vier ganzen Zahlen $N$, $M$, $k$, $D$ in einer Zeile, getrennt durch einzelne Leerzeichen.

Ausgabe

Gib für jeden Testfall die Gesamtzahl der Spiele der Liga in einer eigenen Zeile aus, insgesamt also $T$ Zeilen.

Falls keine Spielzahl die Bedingungen erfüllt, gib $-1$ aus.

Teilaufgaben

1. ($5$ Punkte) $N = 2$
2. ($5$ Punkte) $M = 2$
3. ($5$ Punkte) $k = 1$
4. ($85$ Punkte) Keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

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

Ausgabe 1

54
18
-1