KOI 棒球聯賽有 $N$ 個地區聯賽，

每個地區聯賽有 $M$ 支球隊，因此整個聯賽共有 $N \times M$ 支球隊。

在一個賽季中，每支球隊不僅要與同一地區聯賽的球隊比賽，還要與其他地區聯賽的球隊比賽。

與同一地區聯賽中每支球隊比賽的場數為 $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$ 必須保持不變。

此外，每支球隊必須與其他每支球隊至少比賽一次。

換言之，必須滿足 $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,000$ 組測試案例。

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

* $1 \le k \le 100$

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

輸入格式

第一行給出測試案例的數量 $T$。

接下來 $T$ 行，每行給出一組測試案例的資訊。

每組測試案例在一行中給出四個整數 $N$、$M$、$k$、$D$，相鄰兩數以一個空格分隔。

輸出格式

共輸出 $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