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.


-----Input-----

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.


-----Output-----

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$.


-----Example-----
Input
5
6 7 4
10 7 12
12 30 7
1 1 1
3247834 10298779 625324

Output
6
9
5
0
116461800



-----Note-----

Here are the pairs for the first test case:  $$

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import sys\nimport heapq, functools, collections\nimport math, random\nfrom collections import Counter, defaultdict\n\n# available on Google, not available on Codeforces\n# import numpy as np\n# import scipy\n\n\ndef solve(m,d,w):  # fix inputs here\n    console("----- solving ------")\n\n    a = int(w/math.gcd(w,1-d))\n    b = min(m,d)\n\n    console(a,b)\n\n    return ((1 + b//a)*(b + b%a))//2 - b\n\n\ndef console(*args):  # the judge will not read these print statement\n    print(\'\\033[36m\', *args, \'\\033[0m\', file=sys.stderr)\n    return\n\n# fast read all\n# sys.stdin.readlines()\n\nfor case_num in range(int(input())):\n    # read line as a string\n    # strr = input()\n\n    # read line as an integer\n    # k = int(input())\n    \n    # read one line and parse each word as a string\n    # lst = input().split()\n\n    # read one line and parse each word as an integer\n    m,d,w = list(map(int,input().split()))\n\n    # read matrix and parse as integers (after reading read nrows)\n    # lst = list(map(int,input().split()))\n    # nrows = lst[0]  # index containing information, please change\n    # grid = []\n    # for _ in range(nrows):\n    #     grid.append(list(map(int,input().split())))\n\n    res = solve(m,d,w)  # please change\n    \n    # Google - case number required\n    # print("Case #{}: {}".format(case_num+1, res))\n\n    # Codeforces - no case number required\n    print(res)\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13865