P国的历法比较特殊，每一年都有 $m$ 个月 , 每个月有 $d$ 天。每个星期有 $w$ 天。

每年的第一天也是一个星期的第一天。

求出有多少对 $(x,y)$ , $x < y$ 满足第 $y$ 个月的第 $x$ 天和第 $x$ 个月的第 $y$ 天在一个星期内是同一天。

输入格式

第一行一个整数 $t$ , 表示数据组数。$(1 \leq t \leq 10^3)$

接下来 $t$ 行，每行输入三个整数 $ m,d,w $ , 表示序列的长度 $ ( 1 \leq m,d,w \leq 10^9 ) $。

输出格式

输出 $t$ 行，每行一个整数，表示满足要求二元对的数量。

样例输入

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

样例输出

6
9
5
0
116461800