Берляндский год состоит из \(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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач