La ligue de baseball KOI comprend $N$ ligues régionales,
chacune comptant $M$ équipes, soit $N \times M$ équipes au total.
Au cours d’une saison, chaque équipe doit affronter les équipes de sa ligue régionale ainsi que celles des autres ligues régionales.
Le nombre de matchs contre chaque équipe de la même ligue régionale est $A$, identique pour tous ces adversaires.
Autrement dit, une équipe $X$ joue $A$ matchs contre chaque équipe $Y$ ($Y \ne X$) de sa ligue régionale.
Le nombre de matchs contre chaque équipe des autres ligues régionales est $B$, identique pour tous ces adversaires.
Autrement dit, une équipe $X$ joue $B$ matchs contre chaque équipe $Z$ ($Z \ne X$) des autres ligues régionales.
Les nombres $A$ et $B$ doivent vérifier $A = k \times B$, où $k$ est un entier au moins égal à $1$.
En raison d’une pandémie mondiale, la ligue KOI a décidé de raccourcir la saison de cette année,
en choisissant un nombre total de matchs inférieur ou égal à $D$ et aussi proche que possible de $D$.
Il faut donc redéfinir les nombres $A$ et $B$ de matchs contre chaque équipe de la même ligue régionale et des autres ligues.
Bien entendu, $A = k \times B$ doit rester vérifié et $k$ doit rester inchangé.
De plus, chaque équipe doit affronter toutes les autres au moins une fois.
Autrement dit, $A \ge 1$ et $B \ge 1$ doivent être vérifiés.
Par exemple, pour $N = 2$, $M = 3$, $k = 3$ et la limite $D = 60$, choisir $A = 6$, $B = 2$ donne
$18$ matchs au total entre équipes de ligues régionales différentes et $36$ entre équipes de la même ligue régionale.
La ligue compte donc $54$ matchs, le nouveau total le plus proche de $D$.
Étant donnés le nombre de ligues régionales $N$, le nombre d’équipes par ligue régionale $M$,
l’entier $k$ vérifiant $A = k \times B$ et la nouvelle limite $D$,
écrivez un programme qui calcule et affiche le total de matchs de la ligue inférieur ou égal à $D$ et le plus proche possible de $D$.
[Contraintes]
* Tous les nombres donnés sont des entiers.
* Chaque entrée contient entre $1$ et $1,000$ cas de test à traiter.
* $2 \le N, M \le 100$
* $1 \le k \le 100$
* $1 \le D \le 1,000,000,000$
Entrée
La première ligne contient le nombre de cas de test $T$.
Chacune des $T$ lignes suivantes contient les informations d’un cas de test.
Chaque cas est composé de quatre entiers $N$, $M$, $k$, $D$ sur une ligne, séparés par une seule espace.
Sortie
Affichez le nombre total de matchs de la ligue pour chaque cas sur une ligne distincte, soit $T$ lignes.
Si aucun nombre de matchs ne satisfait les conditions, affichez $-1$.
Sous-tâches
- ($5$ points) $N = 2$
- ($5$ points) $M = 2$
- ($5$ points) $k = 1$
- ($85$ points) Aucune contrainte supplémentaire.
Exemples
Entrée 1
3 2 3 3 60 2 2 1 18 2 2 1 4
Sortie 1
54 18 -1