تضم رابطة KOI للبيسبول $N$ دوريات إقليمية،

وفي كل دوري إقليمي $M$ فرق، ولذلك تضم الرابطة كلها $N \times M$ فريقًا.

خلال الموسم، يجب أن يلعب كل فريق مع فرق دوريّه الإقليمي وكذلك مع فرق الدوريات الإقليمية الأخرى.

عدد المباريات مع كل فريق من الدوري الإقليمي نفسه هو $A$، وهو متساوٍ لجميع هؤلاء الخصوم.

أي إن الفريق $X$ يلعب $A$ مباريات مع كل فريق $Y$ ($Y \ne X$) في الدوري الإقليمي نفسه.

وعدد المباريات مع كل فريق من الدوريات الإقليمية الأخرى هو $B$، وهو متساوٍ لجميع هؤلاء الخصوم.

أي إن الفريق $X$ يلعب $B$ مباريات مع كل فريق $Z$ ($Z \ne X$) في الدوريات الإقليمية الأخرى.

ويجب أن يحقق $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$،

والعدد الصحيح $k$ الذي يحقق $A = k \times B$ والحد الجديد للمباريات $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