E. Calendar Ambiguity
math; number theory
Berland year consists of \(m\) months with \(d\) days each. Months are numbered from \(1\) to \(m\). Berland week consists of \(w\) days. The first day of the year is also the first day of the week. Note that the last week of the year might be shorter than \(w\) days.A pair \((x, y)\) such that \(x < y\) is ambiguous if day \(x\) of month \(y\) is the same day of the week as day \(y\) of month \(x\).Count the number of ambiguous pairs.
The first line contains a single integer \(t\) (\(1 \le t \le 1000\)) — the number of testcases.Each of the next \(t\) lines contains three integers \(m\), \(d\) and \(w\) (\(1 \le m, d, w \le 10^9\)) — the number of months in a year, the number of days in a month and the number of days in a week.
Print \(t\) integers — for each testcase output the number of pairs \((x, y)\) such that \(x < y\) and day \(x\) of month \(y\) is the same day of the week as day \(y\) of month \(x\).
Here are the pairs for the first test case: