题目描述

本题题解已发表至 讨论区

奶龙星球的一年有 $m$ 月，每个月有 $d$ 天，每周有 $w$ 天。保证一年的第一天一定是周一。

求数对 $(x,y)$ 的个数，使得 $x<y$ 且 $x$ 月的第 $y$ 天和 $y$ 月的第 $x$ 天在一周中是同一天。

输入描述

第一行包含单个整数 $t$ （ $1 \le t \le 1000$ ）—测试用例的数量。

接下来的每一行 包含三个整数 $m$ ， $d$ 和 $w$ ( $1 \le m, d, w \le 10^9$ )-一年的月数，一个月的天数和一个星期的天数。

输出描述

对于每个测试样例，输出（x,y）数对的个数。

示例 1

输入

3
12 30 7
6 12 4
11 13 18

输出

5
2
15