A liga de basebol KOI tem $N$ ligas regionais,

cada uma com $M$ equipas, pelo que a liga completa tem $N \times M$ equipas.

Numa época, cada equipa deve jogar com equipas da sua liga regional e também de outras ligas regionais.

O número de jogos contra cada equipa da mesma liga regional é $A$, igual para todos esses adversários.

Ou seja, uma equipa $X$ joga $A$ jogos contra cada equipa $Y$ ($Y \ne X$) da mesma liga regional.

O número de jogos contra cada equipa de outras ligas regionais é $B$, igual para todos esses adversários.

Ou seja, uma equipa $X$ joga $B$ jogos contra cada equipa $Z$ ($Z \ne X$) de outras ligas regionais.

Os valores $A$ e $B$ devem satisfazer $A = k \times B$, sendo $k$ um inteiro pelo menos $1$.

Devido a uma pandemia mundial, a liga KOI decidiu encurtar a época deste ano,

escolhendo um total de jogos não superior a $D$ e tão próximo de $D$ quanto possível.

É, portanto, necessário escolher de novo os números $A$ e $B$ de jogos contra cada equipa da mesma liga regional e de outras ligas.

Naturalmente, deve continuar a verificar-se $A = k \times B$, mantendo $k$ inalterado.

Além disso, cada equipa deve jogar com todas as outras pelo menos uma vez.

Por outras palavras, deve verificar-se $A \ge 1$ e $B \ge 1$.

Por exemplo, para $N = 2$, $M = 3$, $k = 3$ e o limite $D = 60$, escolher $A = 6$, $B = 2$ dá

$18$ jogos no total entre equipas de ligas regionais diferentes e $36$ entre equipas da mesma liga regional.

Assim, o total é de $54$ jogos, o novo total mais próximo de $D$.

Dados o número de ligas regionais $N$, o número de equipas em cada uma $M$,

o inteiro $k$ que satisfaz $A = k \times B$ e o novo limite de jogos $D$,

escreve um programa que calcule e imprima o total de jogos da liga que seja não superior a $D$ e o mais próximo possível de $D$.

[Restrições]

* Todos os números dados são inteiros.

* Cada entrada contém entre $1$ e $1,000$ casos de teste a resolver.

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

* $1 \le k \le 100$

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

Entrada

A primeira linha contém o número de casos de teste $T$.

Cada uma das $T$ linhas seguintes contém a informação de um caso de teste.

Cada caso consiste em quatro inteiros $N$, $M$, $k$, $D$ numa linha, separados por um único espaço.

Saída

Imprime o número total de jogos da liga para cada caso numa linha distinta, num total de $T$ linhas.

Se não existir um número de jogos que satisfaça as condições, imprime $-1$.

Subtarefas

1. ($5$ pontos) $N = 2$
2. ($5$ pontos) $M = 2$
3. ($5$ pontos) $k = 1$
4. ($85$ pontos) Sem restrições adicionais.

Exemplos

Entrada 1

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

Saída 1

54
18
-1