CF1389E Calendar Ambiguity

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: