题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

KOI 棒球联赛有 $N$ 个地区联赛，每个地区联赛有 $M$ 支队伍，因此整个联赛由 $N \times M$ 支队伍构成。

在一个赛季中，每支队伍不仅需要与同一地区联赛的其他队伍进行比赛，还需要与其他地区联赛的队伍进行比赛。与同一地区联赛队伍之间的每队比赛次数记作 $A$，对所有地区联赛都相同。也就是说，某支队伍 $X$ 会与同一地区联赛中的每支其他队伍 $Y$（$X \ne Y$）各进行 $A$ 场比赛。
此外，与其他地区联赛队伍之间的每队比赛次数记作 $B$，也对所有队伍都相同。也就是说，队伍 $X$ 会与所有来自其他地区联赛的队伍 $Z$（$X \ne Z$）各进行 $B$ 场比赛。
但 $A$ 与 $B$ 之间需满足关系：$A = k \times B$，其中 $k$ 是大于等于 1 的整数。

受全球性流行病影响，今年的 KOI 棒球联赛决定缩短赛季，只要总比赛场数不超过 $D$，并尽可能接近 $D$ 即可。因此，需要重新决定 $A$ 与 $B$ 的值，但仍需满足 $A = k \times B$，且 $k$ 不变。此外，每支队伍与其他任何一支队伍至少要有一场比赛，也就是说需满足 $A \geq 1$ 且 $B \geq 1$。

例如，当 $N = 2$，$M = 3$，$k = 3$，最大比赛场数限制 $D = 60$ 时，若设 $A = 6$，$B = 2$，则与其他地区队伍的总比赛场数为 18，与同一地区队伍的总比赛场数为 36，整个联赛的比赛总场数为 54，这就是不超过 $D$ 且最接近 $D$ 的方案。

现在，给定地区联赛数量 $N$，每个地区联赛的队伍数量 $M$，乘积因子 $k$（满足 $A = k \times B$），以及最大比赛数限制 $D$，请编写程序计算出不超过 $D$ 的最大联赛总比赛场数。

输入格式

第一行输入一个整数 $T$，表示测试用例数量。
接下来的 $T$ 行中，每行包含四个整数 $N$、$M$、$k$、$D$，中间用空格隔开。

输出格式

输出共 $T$ 行，每行一个整数，对应每个测试用例的联赛最大总比赛场数。如果不存在满足条件的方案，则输出 $-1$。

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

54
18
-1

提示

约束条件

• 所有给定数据均为整数
• 每组输入数据中，测试用例数量在 1 到 1000 之间
• $2 \leq N, M \leq 100$
• $1 \leq k \leq 100$
• $1 \leq D \leq 1\,000\,000\,000$

子任务

1.（5 分）$N = 2$
2.（5 分）$M = 2$
3.（5 分）$k = 1$
4.（85 分）无附加约束条件