The KOI baseball league has $N$ regional leagues,

and each regional league has $M$ teams, so the entire league operates with $N \times M$ teams.

During a season, every team must play against teams in its own regional league as well as teams in other regional leagues.

The number of games per opposing team in the same regional league is $A$, equal for all such teams.

That is, a team $X$ plays $A$ games against every team $Y$ ($Y \ne X$) in the same regional league.

The number of games per opposing team in other regional leagues is $B$, equal for all such teams.

That is, a team $X$ plays $B$ games against every team $Z$ ($Z \ne X$) in other regional leagues.

Here, $A$ and $B$ must satisfy $A = k \times B$, where $k$ is an integer at least $1$.

Due to a worldwide pandemic, this year's KOI baseball league has decided to shorten its season,

choosing a total number of games at most $D$ and as close to $D$ as possible.

Thus, the numbers $A$ and $B$ of games per opposing team in the same and other regional leagues must be chosen anew.

Of course, $A = k \times B$ must still hold, and $k$ must remain unchanged.

Also, every team must play every other team at least once.

In other words, $A \ge 1$ and $B \ge 1$ must hold.

For example, when $N = 2$, $M = 3$, $k = 3$ and the game limit is $D = 60$, choosing $A = 6$, $B = 2$ gives

$18$ games in total between teams from different regional leagues and $36$ between teams from the same regional league.

Thus, the league has $54$ games in total, the new total closest to $D$.

Given the number $N$ of regional leagues, the number $M$ of teams in each regional league,

the integer $k$ satisfying $A = k \times B$, and the new game limit $D$,

write a program to calculate and print the league's total number of games that is at most $D$ and as close as possible to $D$.

[Constraints]

* All given numbers are integers.

* Each input contains at least $1$ and at most $1,000$ test cases to solve.

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

* $1 \le k \le 100$

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

Input

The first line contains the number of test cases $T$.

Each of the following $T$ lines contains the information for one test case.

Each test case consists of four integers $N$, $M$, $k$, $D$ on one line, separated by single spaces.

Output

Print the league's total number of games for each test case on its own line, for a total of $T$ lines.

If no number of games satisfies the conditions, print $-1$.

Subtasks

1. ($5$ points) $N = 2$
2. ($5$ points) $M = 2$
3. ($5$ points) $k = 1$
4. ($85$ points) No additional constraints.

Examples

Input 1

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

Output 1

54
18
-1