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

Source: codeforces | Difficulty: HARD
Tags: Number theory

Mathematics


Solutions:
def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
for _ in range(int(input())):
	(m, d, w) = map(int, input().split())
	g = w // gcd(d - 1, w)
	c = min(m, d)
	v = c // g
	ans = v * (v - 1) // 2 * g
	ans += (c - g * v) * v
	print(ans)


import os, sys
from io import BytesIO, IOBase
from math import gcd

def main():
	for _ in range(int(input())):
		(m, d, w) = map(int, input().split())
		fac = w // gcd(w, d - 1)
		lim = min(m, d)
		(a, b) = divmod(lim, fac)
		gr = b * (a + 1) * a // 2
		le = (fac - b) * a * (a - 1) // 2
		print(gr + le)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def gcd(x, y):
	if x % y == 0:
		return y
	return gcd(y, x % y)
n = int(input())
for i in range(n):
	(m, d, w) = map(int, input().split())
	z = min(m, d)
	w //= gcd(d - 1, w)
	ans = 0
	fm = z % w
	fn = z // w
	ans += fn * (fn - 1) // 2 * (w - fm) + fn * (fn + 1) // 2 * fm
	print(ans)


from math import gcd
t = int(input())
for j in range(t):
	(a, b, c) = [int(i) for i in input().split()]
	c = c // gcd(c, b - 1)
	a = min(a, b)
	m = a // c
	print(m * a - c * m * (m + 1) // 2)


import sys
sys.setrecursionlimit(2147483647)
input = sys.stdin.readline
import math

def calc(arr):
	(m, d, w) = arr
	max_x = min(m, d)
	if (d - 1) % w == 0:
		return max_x * (max_x - 1) // 2
	else:
		s = math.gcd(d - 1, w)
		w = w // s
		res = max_x % w
		b = max_x // w
		ans = b * (b - 1) // 2 * w + res * b
		return ans
(n, arr) = (int(input()), [])
for _ in range(n):
	arr.append(calc(list(map(int, input().split(' ')))))
for a in arr:
	print(a)


import math
t = int(input())
res = []
for i in range(0, t):
	(m, d, w) = list(map(int, input().split()))
	q = min(m, d)
	n = math.gcd(d - 1, w)
	if n != None:
		s = q // (w // n) * (q // (w // n) + 1) // 2 * (w // n)
		res.append(q * (q // (w // n)) - s)
	else:
		res.append(0)
for i in range(0, t):
	print(res[i])


from sys import stdin, setrecursionlimit as srl
from threading import stack_size, Thread
srl(int(1000000000.0) + 7)
stack_size(int(100000000.0))

def hcf(a, b):
	if a < b:
		(a, b) = (b, a)
	if b == 0:
		return a
	return hcf(b, a % b)

def solve():
	t = int(input())
	for _ in range(t):
		(m, d, w) = map(int, input().split())
		i = 1
		gap = w // hcf(w, d - 1)
		limit = min(d, m)
		var = (limit - 1) // gap
		ans = limit * var - gap * var * (var + 1) // 2
		print(ans)
Thread(target=solve).start()


import math
t = int(input())
for _ in range(t):
	(m, d, w) = map(int, input().split())
	if d == 1:
		print(0)
		continue
	g = w // math.gcd(d - 1, w)
	(m, d) = (min(m, d), max(m, d))
	(x, r) = (m // g, m % g)
	res = (x - 1 + 1) * (x - 1) * g // 2 + r * x
	print(res)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def f(n):
	return n * (n + 1) // 2
for _ in range(int(input())):
	(M, D, W) = map(int, input().split())
	c = W // gcd(D - 1, W)
	m_ = min(D, M)
	n = m_ // c
	print(n * m_ - f(n) * c)


import math
for _ in range(int(input())):
	(m, d, w) = [int(__) for __ in input().split()]
	if d == 1:
		print(0)
		continue
	difference = w * (d - 1) // (math.gcd(w, d - 1) * (d - 1))
	shit = min(m, d)
	x = shit // difference
	ans = x * (shit % difference) + x * (x - 1) * difference // 2
	print(ans)


from math import gcd
tZ = int(input())
for j in range(tZ):
	(k, l, c) = [int(i) for i in input().split()]
	c = c // gcd(c, l - 1)
	k = min(k, l)
	m = k // c
	print(m * k - c * m * (m + 1) // 2)


from math import gcd
for _ in range(int(input())):
	(m, d, w) = list(map(int, input().split()))
	if d == 1:
		print(0)
	else:
		w1 = w // gcd(w, d - 1)
		md = min(m, d)
		mdd_w1 = md // w1
		print((md * 2 - w1 - mdd_w1 * w1) * mdd_w1 // 2)


def gcd(a, b):
	if a % b == 0:
		return b
	else:
		return gcd(b, a % b)
for _ in range(int(input())):
	(m, d, w) = map(int, input().split())
	if d == 1:
		k = 1
	else:
		k = w // gcd(max(w, d - 1), min(w, d - 1))
	p = min(m, d)
	z = p // k
	ans = p * z - k * z * (z + 1) // 2
	print(ans)


from math import gcd
t = int(input())
for _ in range(t):
	(a, b, c) = map(int, input().split())
	k = gcd(c, b - 1)
	c = c // k
	a = min(a, b)
	m = a // c
	print(m * a - c * m * (m + 1) // 2)


import math
from decimal import Decimal
n = int(input())
for i in range(n):
	(m, d, w) = [int(e) for e in input().split(' ')]
	dvd = w // math.gcd(w, d - 1)
	n = min(m, d) // dvd
	s = Decimal(n) / Decimal(2) * (2 * (min(m, d) - dvd) - dvd * (n - 1))
	print(int(s))


from sys import stdin, stdout

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def calender_ambiguity(m, d, w):
	K = (w - d % w) % w
	D = min(d, m)
	if (K + 1) % w == 0:
		if D == 1:
			return 0
		res = D * (D - 1) // 2
	else:
		g = gcd(w, K + 1)
		w //= g
		L = (D - 1) // w
		M = (D - 1) % w + 1
		res = (L - 1) * L * w // 2 + L * M
	return res
t = int(stdin.readline())
for _ in range(t):
	(m, d, w) = map(int, stdin.readline().split())
	ans = calender_ambiguity(m, d, w)
	stdout.write(str(ans) + '\n')


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import ceil, floor
from copy import *
from collections import deque, defaultdict
from collections import Counter as counter
from itertools import combinations
from itertools import permutations as permutate
from bisect import bisect_left as bl
from operator import *
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192
from sys import stderr

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def pow(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def gcd(a, b):
	if a == b:
		return a
	while b > 0:
		(a, b) = (b, a % b)
	return a

def prefix_sum(ar):
	return list(accumulate(ar))

def suffix_sum(ar):
	return list(accumulate(ar[::-1]))[::-1]
from collections import defaultdict

def numberOfSetBits(i):
	i = i - (i >> 1 & 1431655765)
	i = (i & 858993459) + (i >> 2 & 858993459)
	return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 24
sys.setrecursionlimit(100005)

def solve():
	(m, d, w) = sep()
	if d == 1:
		print(0)
		return
	g = gcd(d - 1, w)
	w //= g

	def f(a):
		return a * (a - 1) // 2
	m = min(m, d)
	a = m % w
	b = w - a
	divi = m // w
	t = a * f(divi + 1) + b * f(divi)
	print(t)
testcase(int(inp()))


from math import gcd
A = int(input())
for i in range(A):
	(a, b, c) = [int(j) for j in input().split()]
	c = c // gcd(c, b - 1)
	a = min(a, b)
	p = a // c
	print(p * a - c * p * (p + 1) // 2)


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa = ifa[::-1]

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def linc(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t > f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rinc(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t < f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def ldec(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t < f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rdec(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t > f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def binfun(x):
	c = 0
	for w in arr:
		c += ceil(w / x)
	return c

def lowbit(n):
	return n & -n

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] < self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return prime

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		for v in graph[u]:
			if v not in d or d[v] > d[u] + graph[u][v]:
				d[v] = d[u] + graph[u][v]
				heappush(heap, (d[v], v))
	return d

def GP(it):
	return [(ch, len(list(g))) for (ch, g) in groupby(it)]

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None
t = N()
for i in range(t):
	(m, d, w) = RL()
	if d == 1:
		k = min(m, d)
		ans = k * (k - 1) // 2
	else:
		mi = min(m, d)
		x = gcd(d - 1, w)
		w //= x
		ma = mi // w
		ans = mi * ma - w * ma * (ma + 1) // 2
	print(ans)


from math import gcd
for _ in range(int(input())):
	(m, d, w) = map(int, input().split())
	M = min(m, d)
	W = w // gcd(w, d - 1)
	Q = M // W
	R = M % W
	ans = (W - R) * (Q * (Q - 1) // 2) + R * (Q * (Q + 1) // 2)
	print(ans)


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def sumd(n, d):
	if n < d:
		return 0
	k = n // d
	b = d * k - 1
	return (1 + b // d) * (b // d) // 2 * d + (n - b) * (n // d)

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
for _ in range(II()):
	(m, d, w) = MI()
	p = w // gcd(d - 1, w)
	s = min(d - 1, m - 1)
	e = max(0, s - m + 1)
	print(sumd(s, p) - sumd(e, p))


import io
import os
from math import gcd
DEBUG = False

def solveBrute(M, D, W):
	monthsPerYear = M
	daysPerMonth = D
	daysPerWeek = W
	MX = min(monthsPerYear, daysPerMonth)
	count = 0
	for x in range(MX):
		for y in range(x + 1, MX):
			i = (x * daysPerMonth + y) % daysPerWeek
			j = (y * daysPerMonth + x) % daysPerWeek
			assert (i == j) == ((y - x) * (D - 1) % W == 0)
			if i == j:
				count += 1
	count2 = 0
	for diffs in range(1, MX):
		if diffs * (D - 1) % W == 0:
			count2 += MX - diffs
	assert count == count2
	return count

def solve(M, D, W):
	MX = min(M, D)
	if D == 1:
		return MX * (MX - 1) // 2
	A = D - 1
	B = W
	d = gcd(A, B)
	x = B // d
	y = A // d
	assert x > 0 and y > 0
	assert x * A == B * y
	numLoops = (MX - 1) // x
	countFast = MX * numLoops - numLoops * (numLoops + 1) // 2 * x
	if DEBUG:
		count = 0
		for k in range(1, (MX - 1) // x + 1):
			diffs = k * x
			assert 1 <= diffs <= MX - 1
			count += MX - diffs
		assert count == countFast
	return countFast
if DEBUG:
	for M in range(1, 30):
		for D in range(1, 30):
			for W in range(1, 30):
				assert solve(M, D, W) == solveBrute(M, D, W)
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = int(input())
for tc in range(1, TC + 1):
	(M, D, W) = [int(x) for x in input().split()]
	ans = solve(M, D, W)
	print(ans)


from math import gcd
t = int(input())
for it in range(t):
	(m, d, w) = [int(i) for i in input().split()]
	w = w // gcd(w, d - 1)
	m = min(m, d)
	c = m // w
	print(c * m - w * c * (c + 1) // 2)


from math import gcd
for _ in range(int(input())):
	(m, d, w) = map(int, input().split())
	m = min(m, d)
	d = w // gcd(w, d - 1)
	w = m // d
	print(w * m - w * (w + 1) // 2 * d)


def GCD(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
for i in ' ' * int(input()):
	(m, d, w) = map(int, input().split())
	m = min(m, d)
	g = GCD(d - 1, w)
	ww = w // g
	k = m // ww
	print(k * m - k * (k + 1) // 2 * ww)


def gcd(m, n):
	return gcd(n % m, m) if m and n else m + n

def count_ambiguous_pairs(month_count, month_len, week_len):
	m = min(month_count, month_len)
	if month_len == 1:
		return m * (m - 1) // 2
	d = week_len // gcd(month_len - 1, week_len)
	(q, r) = divmod(m, d)
	return r * q + q * (q - 1) * d // 2
test_count = int(input())
for _ in range(test_count):
	(month_count, month_len, week_len) = map(int, input().split())
	print(count_ambiguous_pairs(month_count, month_len, week_len))


from sys import stdin
import math
tt = int(stdin.readline())
for LOOP in range(tt):
	(m, d, w) = map(int, stdin.readline().split())
	if d == 1 or m == 1:
		print(0)
		continue
	if math.gcd(d - 1, w) == 1:
		cntmax = min(m, d)
		minn = cntmax // w
		minv = w - cntmax % w
		maxn = cntmax // w + 1
		maxv = cntmax % w
		print(minv * (minn * (minn - 1) // 2) + maxv * (maxn * (maxn - 1) // 2))
	else:
		loop = (d - 1) * w // math.gcd(d - 1, w) // (d - 1)
		cntmax = min(m, d)
		w = loop
		if cntmax % w != 0:
			minn = cntmax // w
			minv = w - cntmax % w
			maxn = cntmax // w + 1
			maxv = cntmax % w
			print(minv * (minn * (minn - 1) // 2) + maxv * (maxn * (maxn - 1) // 2))
		else:
			minn = cntmax // w
			minv = w
			print(minv * (minn * (minn - 1) // 2))


from math import gcd as f
for tc in range(int(input())):
	(m, d, w) = input().split(' ')
	(m, d, w) = (int(m), int(d), int(w))
	u = min(m, d)
	a = int(w / f(w, d - 1))
	p = int(u / a)
	q = u % a
	if p % 2 == 0:
		print(q * (p + 1) * int(p / 2) + (a - q) * (p - 1) * int(p / 2))
	else:
		print(q * int((p + 1) / 2) * p + (a - q) * int((p - 1) / 2) * p)


import sys

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s)
	sys.stdout.write('\n')

def wi(n):
	sys.stdout.write(str(n))
	sys.stdout.write('\n')

def wia(a, sep=' '):
	sys.stdout.write(sep.join([str(x) for x in a]))
	sys.stdout.write('\n')
import math

def solve(m, d, w):
	mn = min(m, d)
	s = w // math.gcd(d - 1, w)
	k = mn // s
	ans = mn * k - s * (k * (k + 1) // 2)
	return ans

def main():
	for _ in range(ri()):
		(m, d, w) = ria()
		wi(solve(m, d, w))
main()


import math

def test_case():
	(m, d, w) = map(int, input().split())
	step = w // math.gcd(d - 1, w)
	border = min(m, d)
	count = border // step
	print(border * count - count * (2 * step + (count - 1) * step) // 2)

def main():
	t = int(input())
	while t > 0:
		test_case()
		t -= 1
main()


import sys
import io
import math
import collections
import decimal
import itertools
import bisect
import heapq

def input():
	return sys.stdin.readline()[:-1]
INF = 10 ** 10

def solve(M, D, W):
	if D == 1:
		pass
	w = W // math.gcd(W, D - 1)
	m = min(M, D)
	c = (m - 1) // w
	score = c * m - w * c * (c + 1) // 2
	return score
T0 = int(input())
for _ in range(T0):
	(M, D, W) = map(int, input().split())
	print(solve(M, D, W))


import sys

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
t = int(sys.stdin.readline())
i = 0
while i < t:
	i = i + 1
	(m, d, w) = map(int, sys.stdin.readline().split())
	w = w // gcd(d - 1, w)
	mi = min(m, d)
	x = mi // w
	ans = (2 * (mi - w) - w * (x - 1)) * x // 2
	print(ans)


def gcd(m, n):
	while n:
		(m, n) = (n, m % n)
	return m
for _ in range(int(input())):
	(m, d, w) = map(int, input().split())
	res = 0
	t = (d % w - 1) % w
	gap = w // gcd(w, t)
	a = min(m, d) - gap
	b = (min(d, m) - 1) % gap + 1
	h = (a - b) // gap + 1
	print((a + b) * h >> 1)


import math
for _ in range(int(input())):
	(m, d, w) = map(int, input().split())
	w2 = w // math.gcd(d - 1, w)
	mn = min(d, m)
	k = mn // w2
	print(k * mn - k * (k + 1) * w2 // 2)


def GCD(a, b):
	if b == 0:
		return a
	if a == 0:
		return b
	return GCD(b, a % b)
tc = int(input())
while tc > 0:
	(m, d, w) = [int(x) for x in input().split()]
	g = w // GCD(d - 1, w)
	t = min(d, m)
	k = t // g
	r = t % g
	res = (k - 1) * k // 2 * (g - r)
	if g > 1:
		res += k * (k + 1) // 2 * r
	print(res)
	tc -= 1


import sys
input = sys.stdin.readline
from math import gcd
t = int(input())
for tests in range(t):
	(m, d, w) = map(int, input().split())
	MIN = min(m, d)
	if d == 1:
		print(MIN * (MIN - 1) // 2)
	else:
		mod = w // gcd(w, d - 1)
		(q, r) = divmod(MIN - 1, mod)
		ANS = (q - 1) * q // 2 * mod + (r + 1) * q
		print(ANS)


from math import gcd
c2 = lambda x: x * (x - 1) // 2
for _ in range(int(input())):
	(m, d, w) = map(int, input().split())
	t = min(m, d)
	k = w // gcd(d - 1, w)
	print(c2(t // k) * k + t // k * (t % k))


import math
t = int(input())
for i in range(t):
	(m, d, w) = map(int, input().split())
	if d == 1:
		print(0)
	elif d >= m:
		p = math.gcd(d - 1, w)
		q = w // p
		count = (m - 1) // q
		print(m * count - q * (count * (count + 1) // 2))
	elif d < m:
		p = math.gcd(d - 1, w)
		q = w // p
		count = (d - 1) // q
		print(d * count - q * (count * (count + 1) // 2))


from math import gcd

def sum_of_floor(n, p, q):
	t = gcd(p, q)
	(p, q) = (p // t, q // t)
	s = 0
	z = 1
	while q > 0 and n > 0:
		t = p // q
		s = s + z * t * n * (n + 1) // 2
		p = p - q * t
		t = n // q
		s = s + z * p * t * (n + 1) - z * t * (p * q * t + p + q - 1) // 2
		n = n - q * t
		t = n * p // q
		s = s + z * t * n
		n = t
		(p, q) = (q, p)
		z = -z
	return s

def solve():
	(m, d, w) = map(int, input().split())
	if d == 1:
		print(0)
		return
	u = gcd(d - 1, w)
	res = sum_of_floor(min(m, d) - 1, 1, w // u)
	print(res)
t = int(input())
for _ in range(t):
	solve()


from sys import setrecursionlimit as srl
from math import gcd
srl(2147483647)

def calc(arr):
	(m, d, w) = arr
	max_x = min(m, d)
	return max_x * (max_x - 1) // 2 if (d - 1) % w == 0 else max_x // (w // gcd(d - 1, w)) * (max_x // (w // gcd(d - 1, w)) - 1) // 2 * (w // gcd(d - 1, w)) + max_x % (w // gcd(d - 1, w)) * (max_x // (w // gcd(d - 1, w)))
(n, arr) = (int(input()), [])
for _ in range(n):
	arr.append(calc(list(map(int, input().split(' ')))))
for a in arr:
	print(a)


from bisect import bisect_left, bisect_right

class Result:

	def __init__(self, index, value):
		self.index = index
		self.value = value

class BinarySearch:

	def __init__(self):
		pass

	@staticmethod
	def greater_than(num: int, func, size: int=1):
		if isinstance(func, list):
			index = bisect_right(func, num)
			if index == len(func):
				return Result(None, None)
			else:
				return Result(index, func[index])
		else:
			(alpha, omega) = (0, size - 1)
			if func(omega) <= num:
				return Result(None, None)
			while alpha < omega:
				if func(alpha) > num:
					return Result(alpha, func(alpha))
				if omega == alpha + 1:
					return Result(omega, func(omega))
				mid = (alpha + omega) // 2
				if func(mid) > num:
					omega = mid
				else:
					alpha = mid

	@staticmethod
	def less_than(num: int, func, size: int=1):
		if isinstance(func, list):
			index = bisect_left(func, num) - 1
			if index == -1:
				return Result(None, None)
			else:
				return Result(index, func[index])
		else:
			(alpha, omega) = (0, size - 1)
			if func(alpha) >= num:
				return Result(None, None)
			while alpha < omega:
				if func(omega) < num:
					return Result(omega, func(omega))
				if omega == alpha + 1:
					return Result(alpha, func(alpha))
				mid = (alpha + omega) // 2
				if func(mid) < num:
					alpha = mid
				else:
					omega = mid
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def pre(s):
	n = len(s)
	pi = [0] * n
	for i in range(1, n):
		j = pi[i - 1]
		while j and s[i] != s[j]:
			j = pi[j - 1]
		if s[i] == s[j]:
			j += 1
		pi[i] = j
	return pi

def prod(a):
	ans = 1
	for each in a:
		ans = ans * each
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(input()) if True else 1):
	(m, d, w) = map(int, input().split())
	p = min(d, m)
	ans = 0
	req = w // gcd(d - 1, w)
	if p - 1 < req:
		print(0)
		continue
	highest = (p - 1) // req
	print(p * highest - req * highest * (highest + 1) // 2)


import math
for _ in range(int(input())):
	(m, d, w) = map(int, input().split())
	x = min(m, d)
	g = int(w / math.gcd(d - 1, w))
	f = int(x / g)
	print(x * f - f * (f + 1) // 2 * g)


import math
for _ in range(int(input())):
	(m, d, w) = map(int, input().split())
	u = min(m, d)
	w //= math.gcd(w, d - 1)
	k = int(u / w)
	C1 = k * (k - 1) // 2
	C2 = k * (k + 1) // 2
	ans = C2 * (u % w) + C1 * (w - u % w)
	print(ans)


from sys import stdin, gettrace
from math import gcd
if gettrace():
	inputi = input
else:

	def input():
		return next(stdin)[:-1]

	def inputi():
		return stdin.buffer.readline()

def solve():
	(m, d, w) = map(int, inputi().split())
	mxdm = min(m, d)
	g = gcd(d - 1, w)
	n = w // g
	res = mxdm * (mxdm // n) - mxdm // n * (mxdm // n + 1) * n // 2
	print(res)

def main():
	t = int(inputi())
	for _ in range(t):
		solve()
main()


from math import gcd

def lcm(a, b):
	return a * b // gcd(a, b)
t = int(input())
for _ in range(t):
	(m, d, w) = map(int, input().split())
	mi = min(m, d)
	if d == 1:
		print(mi * (mi - 1) // 2)
		continue
	l = lcm(w, d - 1)
	diff = l // (d - 1)
	total = 0
	more_count = mi % diff
	more_per = mi // diff + 1
	total += more_per * (more_per - 1) // 2 * more_count
	full_count = diff - more_count
	full_per = more_per - 1
	total += full_per * (full_per - 1) // 2 * full_count
	print(total)


import sys
input = sys.stdin.readline
import math

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input().strip()
	return list(s[:len(s)])

def invr():
	return map(int, input().strip().split())

def from_file(f):
	return f.readline

def gcd(a, b):
	if b > a:
		(a, b) = (b, a)
	r = a % b
	if r == 0:
		return b
	return gcd(r, b)

def solve(m, d, w):
	if d > 1:
		w //= gcd(w, d - 1)
	mn = min(m, d)
	C = mn // w
	res = C * mn - w * ((1 + C) * C) // 2
	return res
t = inp()
for _ in range(t):
	(m, d, w) = invr()
	print(solve(m, d, w))


t = int(input())
from math import gcd
for _ in range(t):
	(m, d, w) = map(int, input().split())
	z = min(d, m)
	d -= 1
	if d % w == 0:
		print(z * (z - 1) // 2)
		continue
	w //= gcd(d, w)
	z -= 1
	x = z // w
	y = z % w + 1
	print(x * (x - 1) // 2 * (w - y) + (x + 1) * x // 2 * y)


import sys
input = sys.stdin.readline
from math import gcd
t = int(input())
for ccc in range(t):
	(n, k, z) = list(map(int, input().split()))
	g = gcd(k - 1, z)
	c = 0
	mm = min(k, n)
	period = 0
	nums = [1, z]
	for j in range(2, int(mm ** 0.5) + 1):
		if z % j == 0:
			nums.append(j)
			nums.append(z // j)
	nums.sort()
	period = z // g
	if period != 0:
		tt = mm // period
		c += tt * (tt - 1) // 2
		c *= period
		c += mm % period * tt
	else:
		c = 0
	print(c)


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	from math import gcd
	input = sys.stdin.readline
	for _ in range(int(input())):
		(m, d, w) = map(int, input().split())
		g = gcd(w, d - 1)
		v = w // g
		md = min(m, d)
		n = md // v
		a = md % v
		b = v - a
		ans = (n + 1) * n // 2 * a + n * (n - 1) // 2 * b
		print(ans)
main()


def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def calendar():
	t = int(input())
	for i in range(t):
		(m, d, w) = map(int, input().split())
		w2 = w // gcd(w, d - 1)
		m2 = min(m, d)
		x = m2 // w2
		print(x * m2 - x * (x + 1) // 2 * w2)
calendar()


import math
t = int(input())
for _ in range(t):
	(m, d, w) = [int(s) for s in input().split()]
	M = min(m, d)
	if d == 1:
		print(M * (M - 1) // 2)
		continue
	w //= math.gcd(w, d - 1)
	all_val = M // w
	up_idx = M % w
	print(up_idx * (all_val + 1) * all_val // 2 + (w - up_idx) * (all_val - 1) * all_val // 2)


from math import gcd
cmb = lambda x: x * (x - 1) // 2
T = int(input())
for _ in range(T):
	(m, d, w) = map(int, input().split())
	if d == 1:
		print(0)
		continue
	g = gcd(d - 1, w)
	a = w // g
	(p, q) = divmod(min(m, d), a)
	res = 0
	res += q * cmb(p + 1)
	res += (a - q) * cmb(p)
	print(res)


import sys
input = sys.stdin.readline
aaaa = list()
for kek in range(int(input())):
	(m, d, w) = map(int, input().split())
	g = min(m, d)
	d -= 1
	i = 2
	while i < d ** (1 / 2) + 2:
		if d % i == 0:
			d //= i
			if w % i == 0:
				w //= i
		else:
			i += 1
	if d != 0:
		if w % d == 0:
			w //= d
	k = g // w
	ans = g * k - w * k * (k + 1) // 2
	print(ans)


def gcd(a, b):
	while b > 0:
		(a, b) = (b, a % b)
	return a
for t in range(int(input())):
	(yearLen, monthLen, weekLen) = map(int, input().split(' '))
	if yearLen == 1:
		print(0)
		continue
	com = gcd(weekLen, monthLen - 1)
	rem = weekLen // com
	mv = min(yearLen, monthLen)
	maxDiag = mv - rem
	if maxDiag <= 0:
		print(0)
		continue
	full = maxDiag // rem
	rest = maxDiag % rem
	ans = rem * full * (full + 1) // 2 + rest * (full + 1)
	print(ans)


def gcd(x, y):
	if x % y == 0:
		return y
	return gcd(y, x % y)
t = int(input())
for _ in range(t):
	(m, d, w) = map(int, input().split())
	limit = min(m, d)
	a = w // gcd(w, d - 1) if d > 1 else 1
	num = limit // a
	(head, root) = (limit - a, limit - a * num)
	print((head + root) * num // 2)


import math
for t in range(int(input())):
	(m, d, w) = map(int, input().split())
	diffw = w // math.gcd(d - 1, w)
	totp = min(m, d)
	print(totp // diffw * diffw * (totp // diffw - 1) // 2 + totp % diffw * (totp // diffw))


from math import sqrt, gcd

def solve():
	(m, d, w) = map(int, input().split())
	if d == 1:
		print(0)
		return 0
	k = gcd(d - 1, w)
	ww = w // k
	dd = min(m, d)
	qq = dd // ww
	res = +dd * qq - (qq + 1) * qq * ww // 2
	print(res)
for i in range(int(input())):
	solve()


import math
forprint = []

def solve_brute(m, d, w):
	mn = min(m, d)
	ww = w // math.gcd(w, d - 1)
	sol = 0
	for i in range(1, mn // ww + 1):
		sol += mn - i * ww
	forprint.append(str(sol))

def brute():
	t = int(input())
	while t:
		(m, d, w) = map(int, input().split())
		solve_brute(m, d, w)
		t -= 1

def solve(m, d, w):
	mn = min(m, d)
	ww = w // math.gcd(w, d - 1)
	total = mn // ww
	sol = total * mn - ww * total * (total + 1) // 2
	forprint.append(str(sol))

def main():
	t = int(input())
	while t:
		(m, d, w) = map(int, input().split())
		solve(m, d, w)
		t -= 1
main()
print('\n'.join(forprint))


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
ans = []
for _ in range(int(input())):
	(m, d, w) = map(int, input().split())
	g = gcd(d - 1, w)
	w1 = w // g
	mn = min(m, d)
	ans.append((2 * (mn - w1) - w1 * (mn // w1 - 1)) * (mn // w1) // 2)
print('\n'.join(map(str, ans)))


import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda : readline().rstrip()
ni = lambda : int(readline().rstrip())
nm = lambda : map(int, readline().split())
nl = lambda : list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def solve():
	(m, d, w) = nm()
	g = w // gcd(d - 1, w)
	c = min(m, d)
	v = c // g
	ans = v * (v - 1) // 2 * g
	ans += (c - g * v) * v
	print(ans)
	return
T = ni()
for _ in range(T):
	solve()


def gcd(x, y):
	if x % y == 0:
		return y
	return gcd(y, x % y)
t = int(input())
for you in range(t):
	l = input().split()
	m = int(l[0])
	d = int(l[1])
	w = int(l[2])
	if d == 1:
		print(min(m * (m - 1) // 2, d * (d - 1) // 2))
		continue
	g = gcd(d - 1, w)
	mul = w // g
	k = min(m, d)
	n = (min(m, d) - 1) // mul
	print(k * n - n * (n + 1) * mul // 2)


import functools

def factorint(n):
	factors = {}
	m = (n & -n).bit_length() - 1
	if m:
		factors[2] = m
		n >>= m
	m = 0
	while n % 3 == 0:
		n //= 3
		m += 1
	if m:
		factors[3] = m
	d = 5
	while d * d <= n:
		m = 0
		while n % d == 0:
			n //= d
			m += 1
		if m:
			factors[d] = m
		d += 2
		m = 0
		while n % d == 0:
			n //= d
			m += 1
		if m:
			factors[d] = m
		d += 4
	if n > 1:
		factors[n] = 1
	return factors
for t in range(int(input())):
	(m, d, w) = map(int, input().split())
	u = min(m, d)
	if d == 1:
		a = 1
	else:
		f = factorint(w)
		for (k, v) in factorint(d - 1).items():
			if k in f:
				f[k] = max(0, f[k] - v)
		a = functools.reduce(int.__mul__, (k ** v for (k, v) in f.items()), 1)
	m = u // a
	total = u * m - a * (1 + m) * m // 2
	print(total)


import sys
import math

def gcd(a, b):
	if a > b:
		(a, b) = (b, a)
	if b % a == 0:
		return a
	return gcd(b % a, a)
read = sys.stdin.buffer.read
readlines = sys.stdin.buffer.readlines
t = int(input())
for case in range(t):
	(m, d, w) = map(int, input().split())
	if d == 1:
		print(min(d, m) * (min(d, m) - 1) // 2)
	elif m == 1:
		print(0)
	else:
		div = w // gcd(w, d - 1)
		k = (min(m, d) - 1) // div
		print(min(m, d) * k - div * k * (k + 1) // 2)


import sys
import math
T = int(sys.stdin.readline().strip())
for t in range(0, T):
	(m, d, w) = list(map(int, sys.stdin.readline().strip().split()))
	w = w // math.gcd(w, d - 1)
	d = min(d, m)
	m = d
	ans = -d
	ans = ans + m // w * d
	m = m - m // w * w
	ans = ans + d // w * m
	d = d - d // w * w
	ans = ans + d
	print(ans // 2)


import math
t = int(input())
for _ in range(t):
	(m, d, w) = map(int, input().split())
	w = w // math.gcd(w, d - 1)
	mn = min(m, d)
	c = mn // w
	ans = (2 * (mn - w) - w * (c - 1)) * c // 2
	print(ans)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
from collections import defaultdict
from itertools import permutations
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def GCD(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
for i in ' ' * int(input()):
	(m, d, w) = map(int, input().split())
	m = min(m, d)
	g = GCD(d - 1, w)
	ww = w // g
	k = m // ww
	print(k * m - k * (k + 1) // 2 * ww)


import math
t = int(input())
for i in range(t):
	(m, d, w) = map(int, input().split())
	factor = w // math.gcd(w, d - 1)
	upper = min(m, d)
	iterations = upper // factor
	ambi = upper * iterations - factor * iterations * (iterations + 1) // 2
	print(ambi)


from sys import stdin
from math import gcd
input = stdin.buffer.readline

def f(x):
	return x * (x - 1) // 2
for _ in range(int(input())):
	(m, d, w) = map(int, input().split())
	mn = min(d, m)
	if (d - 1) % w == 0:
		print(f(mn))
	else:
		k = w // gcd(w, d - 1)
		print(mn % k * f(mn // k + 1) + (k - mn % k) * f(mn // k))


def gcd(a: int, b: int) -> int:
	while b:
		(a, b) = (b, a % b)
	return a
t = int(input())
for _ in range(t):
	(m, d, w) = map(int, input().split())
	gcd_ = gcd(d - 1, w)
	w = w // gcd_
	min_dm = min(d, m)
	ans = 0
	cnt = (min_dm - 1) // w
	ans += cnt * min_dm
	ans -= w * cnt * (cnt + 1) // 2
	print(ans)


import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default='z', func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
for ik in range(int(input())):
	(m, d, w) = map(int, input().split())
	p = min(d, m)
	w //= math.gcd(d - 1, w)
	ans = p // w * p - w * (p // w) * (p // w + 1) // 2
	print(ans)


import sys
import heapq, functools, collections
import math, random
from collections import Counter, defaultdict

def solve(m, d, w):
	console('----- solving ------')
	a = int(w / math.gcd(w, 1 - d))
	b = min(m, d)
	console(a, b)
	return (1 + b // a) * (b + b % a) // 2 - b

def console(*args):
	print('\x1b[36m', *args, '\x1b[0m', file=sys.stderr)
	return
for case_num in range(int(input())):
	(m, d, w) = list(map(int, input().split()))
	res = solve(m, d, w)
	print(res)


from math import gcd
t = int(input())
for _ in range(t):
	(m, d, w) = map(int, input().split())
	k = w // gcd(w, d - 1)
	p = min(m, d)
	(q, r) = divmod(p, k)
	print(q * (q - 1) // 2 * k + r * q)


def gcd(a, b):
	return a if b == 0 else gcd(b, a % b)
T = int(input())
for test in range(T):
	(m, d, w) = [int(x) for x in input().split()]
	v = w // gcd(w, d - 1)
	L = min(m, d)
	max = (L - 1) // v
	ans = v * (max - 1) * max // 2 + max * (L - 1 - max * v + 1)
	print(ans)


import math
t = int(input())

def solve(m, d, w):
	k = math.gcd(w, d - 1)
	w = w // k
	m = min(m, d)
	c = m // w
	print(int(c * m - w * c * (c + 1) // 2))
while t:
	t -= 1
	(m, d, w) = map(int, input().split())
	solve(m, d, w)


import math
t = int(input())
for _ in range(t):
	(m, d, w) = map(int, input().split())
	l = min(m, d)
	if (d - 1) % w == 0:
		print(l * (l - 1) // 2)
	else:
		gcd = math.gcd(w, d - 1)
		w2 = w // gcd
		a = l - w2
		if a > 0:
			b = l % w2
			c = l // w2
			print((a + b) * c // 2)
		else:
			print(0)