Берляндский год состоит из $$$m$$$ месяцев, в каждом месяце по $$$d$$$ дней. Месяца пронумерованы от $$$1$$$ до $$$m$$$. Берляндская неделя состоит из $$$w$$$ дней. Первый день года также является и первым днем недели. Обратите внимание, что последняя неделя года может быть короче $$$w$$$ дней.
Пара $$$(x, y)$$$ такая, что $$$x < y$$$, неоднозначна, если день $$$x$$$ месяца $$$y$$$ выпадает на тот же день недели, что и день $$$y$$$ месяца $$$x$$$.
Посчитайте количество неоднозначных пар.
В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.
В каждой из следующих $$$t$$$ строк записаны по три целых числа $$$m$$$, $$$d$$$ and $$$w$$$ ($$$1 \le m, d, w \le 10^9$$$) — количество месяцев в году, количество дней в месяце и количество дней в неделе.
Выведите $$$t$$$ целых чисел — на каждый набор входных данных выведите количество пар $$$(x, y)$$$ таких, что $$$x < y$$$, и день $$$x$$$ месяца $$$y$$$ выпадает на тот же день недели, что и день $$$y$$$ месяца $$$x$$$.
5 6 7 4 10 7 12 12 30 7 1 1 1 3247834 10298779 625324
6 9 5 0 116461800
Пары для первого набора входных данных:
