KOI 野球リーグには $N$ 個の地域リーグがあり、

各地域リーグには $M$ チームがあるので、全体では $N \times M$ チームで運営されています。

1 シーズン中、各チームは同じ地域リーグのチームだけでなく、他の地域リーグのチームとも試合を行います。

同じ地域リーグの各チームとの試合数は $A$ で、すべての対戦相手について同じです。

つまり、チーム $X$ は同じ地域リーグのすべてのチーム $Y$（$Y \ne X$）とそれぞれ $A$ 回対戦します。

他の地域リーグの各チームとの試合数は $B$ で、それらすべての対戦相手について同じです。

つまり、チーム $X$ は他の地域リーグのすべてのチーム $Z$（$Z \ne X$）とそれぞれ $B$ 回対戦します。

ただし、$A$ と $B$ は $A = k \times B$ を満たす必要があり、$k$ は $1$ 以上の整数です。

世界的なパンデミックの影響で、今年の KOI 野球リーグはシーズンを短縮し、

リーグ全体の試合数が $D$ 以下で、できるだけ $D$ に近くなるように決めました。

そこで、同じ地域リーグの各チームとの試合数 $A$ と、他の地域リーグの各チームとの試合数 $B$ を新たに決める必要があります。

もちろん、$A = k \times B$ を満たし、$k$ は変えずに維持する必要があります。

また、各チームは他のすべてのチームと少なくとも 1 回は対戦する必要があります。

つまり、$A \ge 1$、$B \ge 1$ を満たす必要があります。

例えば $N = 2$、$M = 3$、$k = 3$ で試合数制限が $D = 60$ のとき、$A = 6$、$B = 2$ とすると、

異なる地域リーグ間の試合数は合計 $18$、同じ地域リーグ内の試合数は合計 $36$ です。

したがってリーグ全体の試合数は $54$ となり、これが $D$ に最も近い新しい試合数です。

地域リーグの個数 $N$、各地域リーグのチーム数 $M$、

$A = k \times B$ を満たす整数 $k$ と、新しい試合数制限 $D$ が与えられたとき、

$D$ 以下で、$D$ に最も近いリーグ全体の試合数を計算して出力するプログラムを作成してください。

[制約]

* 与えられる数はすべて整数です。

* 1 つの入力で $1$ 個以上 $1,000$ 個以下のテストケースを処理します。

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

* $1 \le k \le 100$

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

入力

最初の行にテストケース数 $T$ が与えられます。

続く $T$ 行には、各行に 1 つのテストケースの情報が与えられます。

各テストケースは、1 行に 4 つの整数 $N$、$M$、$k$、$D$ が 1 個の空白で区切って与えられます。

出力

各テストケースについてリーグの全試合数を 1 行に出力し、合計 $T$ 行出力してください。

条件を満たす試合数が存在しない場合は $-1$ を出力してください。

小課題

1. ($5$ 点) $N = 2$
2. ($5$ 点) $M = 2$
3. ($5$ 点) $k = 1$
4. ($85$ 点) 追加の制約はありません。

入出力例

入力 1

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

出力 1

54
18
-1