Calendar

Problem Description

The calendar of country P is special: every year has $m$ months, and every month has $d$ days. Every week has $w$ days.

The first day of the year is also the first day of a week.

Find the number of pairs $(x, y)$ with $x < y$ such that day $x$ of month $y$ and day $y$ of month $x$ fall on the same weekday.

Input Format

The first line contains an integer $t$, the number of test cases ($1 \le t \le 10^3$).

The next $t$ lines each contain three integers $m, d, w$ ($1 \le m, d, w \le 10^9$).

Output Format

Output $t$ lines, each containing a single integer: the number of valid pairs.

Sample Input

5
6 7 4
10 7 12
12 30 7
1 1 1
3247834 10298779 625324

Sample Output

6
9
5
0
116461800