Harvey Specter has agreed to take Mike Ross to a meeting filled with brilliant scientists at NSA Headquarters. But, as always, it's not going to be easy for Mike. He has to solve a puzzle given by Harvey. 

Harvey gives two numbers N and K and defines a set A.

A = { x : x is a natural number ≤ N } 

(i.e), A = {1,2,3,4,5,6,...., N}   

Mike has to find the total number of pairs of elements A[i] and A[j] belonging to the given set, such that, i < j and their sum is divisible by K

Input Format 

An integer T followed by T lines, each containing a pair of space separated integers N and K. 

Output Format 

T integers on separate lines. Each integer denotes the answer corresponding to that test case.

Constraints 

1<=T<=100 

K<=N<=10^{9} 

1<=K<=10000  

Sample Input  

2
10 4
7 3

Sample Output

10
7

Explanation  

For the 1^{st} test case, there are 10 pairs whose sum is divisible by 4. 

(1,3), (1,7), (2,6), (2,10), (3,5), (3,9), (4,8), (5,7), (6,10) and (7,9)

For the 2^{nd} test case, there are 7 pairs whose sum is divisible by 3. 

(1,2), (1,5), (2,4), (2,7), (3,6), (4,5) and (5,7)

Difficulty: MEDIUM_HARD
Tags: Number theory

Starter code:

Solutions:
T = int(input())
for i in range(T):
	(N, K) = [int(j) for j in input().split()]
	a = N // K
	b = 2 * N // K
	count = 0
	count += K * a * (a + 1) / 4 - a / 2
	count += N * (b - a) + (b - a) / 2 - K * (b * (b + 1) / 2 - a * (a + 1) / 2) / 2
	if K % 2 == 0:
		count -= b / 2
	else:
		count -= b / 4
	print(round(count))


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	total = 0
	a = N // K + 1
	b = 2 * N // K - (1 if 2 * N % K == 0 else 0)
	if K % 2 == 0:
		total += K * b * (b + 1) // 4 - b
	elif b % 2 == 0:
		total += K * b * (b + 2) // 8 - b // 2
		total += K * b * (b + 2) // 8 - b * (K + 1) // 4
	else:
		total += K * (b - 1) * (b + 1) // 8 - (b - 1) // 2
		total += K * (b + 1) * (b + 3) // 8 - (b + 1) * (K + 1) // 4
	total -= (b - a + 1) * ((a + b) * K - 2 * (N + 1)) // 2
	print(total)


T = int(input())
for t in range(T):
	s = input()
	(N, K) = s.split()
	N = int(N)
	K = int(K)
	a = [0] * K
	a[0] = N // K
	for i in range(1, N % K + 1):
		a[i] = a[0] + 1
	for i in range(N % K + 1, K):
		a[i] = a[0]
	count = 0
	count = a[0] * (a[0] - 1) // 2
	loop = K // 2
	if K % 2 != 0:
		loop = K // 2 + 1
	for i in range(1, loop):
		count += a[i] * a[K - i]
	if K % 2 == 0:
		count += a[K // 2] * (a[K // 2] - 1) // 2
	print(count)


num = input()
num = int(num)
lines = []
for i in range(num):
	lines.append(input())
import math
for i in range(num):
	lines[i] = lines[i].split(' ')
	N = int(lines[i][0])
	K = int(lines[i][1])
	g_sum = 2 * N - 1
	mults = int(g_sum / K)
	in_range = int(N / K)
	if K % 2 == 0:
		pairs = (2 * K + (in_range - 1) * K) * in_range / 4 - in_range
	else:
		even_num = int(in_range / 2)
		odd_num = in_range - even_num
		even_sum = (4 * K + (even_num - 1) * 2 * K) * even_num / 4 - even_num
		odd_sum = (2 * K + (odd_num - 1) * 2 * K) * odd_num / 4 - odd_num / 2
		pairs = even_sum + odd_sum
	sseq_len = mults - in_range
	even_num = int(sseq_len / 2)
	odd_num = sseq_len - even_num
	if K % 2 == 0:
		pairs += N * sseq_len - (2 * K * (in_range + 1) + (sseq_len - 1) * K) * sseq_len / 4
	else:
		even_sum = (2 * K * (in_range + 2) + (even_num - 1) * 2 * K) * even_num / 4
		odd_sum = (2 * K * (in_range + 1) + (odd_num - 1) * 2 * K) * odd_num / 4 - odd_num / 2
		pairs += N * sseq_len - (even_sum + odd_sum)
	print(int(pairs))


import sys

def calcnumsq(num):
	return num * (num - 1) // 2

def solve(n, k):
	if k == 1:
		return calcnumsq(n)
	else:
		a = n // k
		b = n % k

		def getvaltocalc(num):
			if num <= b:
				return a + 1
			else:
				return a

		def printnum():
			print('n={0} k={1} a={2} b={3}'.format(n, k, a, b))
			strtemp = ''
			for i in range(k):
				strtemp += '{0}:{1}, '.format(i, getvaltocalc(i))
			print(strtemp)
		if k == 2:
			if n % 2 == 0:
				return calcnumsq(a) * 2
			else:
				return calcnumsq(a) + calcnumsq(a + 1)
		else:
			loopmax = k // 2 + 1
			count = 0
			for i in range(loopmax):
				addval = 0
				if i == 0:
					addval = calcnumsq(a)
				else:
					vala = getvaltocalc(i)
					valb = getvaltocalc(k - i)
					if i == k - i:
						addval = calcnumsq(vala)
					else:
						addval = vala * valb
				count += addval
			return count

def main():
	for i in range(int(sys.stdin.readline())):
		temp = sys.stdin.readline().split()
		(n, k) = (int(temp[0]), int(temp[1]))
		ret = solve(n, k)
		print(ret)
main()


def SOLVE():
	(n, k) = input().split(' ')
	n = int(n)
	k = int(k)
	t = n // k
	l = [t for i in range(0, k)]
	t = n - k * t
	for i in range(1, t + 1):
		l[i] += 1
	ans = l[0] * (l[0] - 1) // 2
	if k % 2 == 0:
		ans += l[k // 2] * (l[k // 2] - 1) // 2
		m = k // 2
		m = m - 1
	else:
		m = k // 2
	i = 1
	while i <= m:
		ans += l[i] * l[k - i]
		i += 1
	print(ans)
x = int(input())
while x > 0:
	x -= 1
	SOLVE()


import sys
t = int(sys.stdin.readline())
numbers = sys.stdin.readlines()
for i in numbers:
	(n, k) = map(int, i.split())
	a = n // k
	b = (2 * n - 1) // k
	first_half = (k * a * (a + 1) - 2 * a) / 4
	if k % 2 == 0:
		first_half -= a / 2
	else:
		first_half -= 0.5 * (a // 2)
	ba = b - a
	ba1 = b - a - 1
	second_half = n * ba + ba / 2 - k / 4 * (b * (b + 1) - a * (a + 1))
	if k % 2 == 0:
		second_half -= ba / 2
	elif (a + 1) % 2 == 0:
		second_half -= 0.5 * (1 + ba1 // 2)
	else:
		second_half -= 0.5 * ((ba1 + 1) // 2)
	print(int(first_half + second_half))


T = int(input())
for test in range(T):
	(N, K) = map(int, input().split())
	huh = {}
	for i in range(K):
		huh[(N - i) % K] = N - i
	total = 0
	for i in range(1, K + 1):
		n = int(huh[K - i] / K) + 1
		if i >= K / 2:
			n -= 1
			if i == K:
				n -= 1
		cur = int(n * (n + 1) / 2)
		if cur >= 0:
			total += cur
	print(total)


def calcFast(n, k):
	x = n // k
	y = x & 1 and x // 2 + 1 or x // 2
	p = calc(k)
	q = calc(k * (x & 1 and x or x - 1))
	r = (p + q) * y // 2
	p = calc(k + k)
	q = calc(k * (x & 1 and x or x - 1) + (x & 1 and -k or k))
	r += (p + q) * (x - y) // 2
	return r

def calc(n):
	return n // 2 if n & 1 else n // 2 - 1

def process(n, k):
	threshold = n + 1
	total = calcFast(2 * n - 1, k)
	(start, end) = ((threshold // k + 1) * k, n * 2 - 1)
	count = (end - start) // k + 1
	realEnd = start + k * (count - 1)
	minus = (start + realEnd - threshold * 2) * count // 2
	total -= minus
	return total

def main():
	n = int(input().strip())
	for line in range(n):
		(N, K) = map(int, input().strip().split())
		print(process(N, K))
main()


def solution(n, k):
	import math
	packs_c = n // k + 1
	full_packs_c = packs_c - 1
	last_pack_elements = n % k
	inside_one_pack = math.ceil((k - 2) / 2)
	inside_full_packs = inside_one_pack * full_packs_c
	between_full_packs = k * (packs_c - 2) * (packs_c - 1) // 2
	last_pack_and_full_packs = last_pack_elements * full_packs_c
	if last_pack_elements > inside_one_pack and k % 2 == 1:
		inside_last_pack = last_pack_elements - inside_one_pack
	elif last_pack_elements > inside_one_pack and k % 2 == 0:
		inside_last_pack = last_pack_elements - 1 - inside_one_pack
	else:
		inside_last_pack = 0
	return inside_full_packs + between_full_packs + last_pack_and_full_packs + inside_last_pack

def main():
	cases = int(input())
	for _ in range(cases):
		(n, k) = tuple((int(x) for x in input().split(' ')))
		print(solution(n, k))
main()


def res(n, k, r):
	return (n + k - r) // k

def cnt(n):
	return n * (n - 1) // 2
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	ret = 0
	for r1 in range(k):
		r2 = k - r1
		(a, b) = (res(n, k, r1), res(n, k, r2))
		if r1 == 0:
			a -= 1
			b -= 1
		if r1 < r2:
			ret += cnt(min(a, b) + 1)
		else:
			ret += cnt(min(a, b))
		if b > a:
			ret += a
	print(ret)


t = int(input())
for j in range(t):
	(n, k) = input().split()
	(n, k) = [int(n), int(k)]
	a = []
	for i in range(k):
		if i <= n % k and i != 0:
			a.append(n // k + 1)
		else:
			a.append(n // k)
	count = a[0] * (a[0] - 1) // 2
	if k % 2 == 0:
		count += a[k // 2] * (a[k // 2] - 1) // 2
		l = k // 2
	else:
		l = (k + 1) // 2
	for i in range(1, l):
		count += a[i] * a[k - i]
	print(count)


x = int(input())

def single(a):
	if a != 1:
		x = a * (a - 1) // 2
		return x
	else:
		return 0
for i in range(x):
	x = input()
	x = x.split()
	for i in range(len(x)):
		x[i] = int(x[i])
	base = x[0] // x[1]
	counters = [base for i in range(x[1])]
	modOverflow = x[0] - base * x[1]
	for i in range(1, modOverflow + 1):
		counters[i] += 1
	answer = single(counters[0])
	if x[1] % 2 == 0:
		answer += single(counters[x[1] // 2])
		counters[x[1] // 2] = 0
	for i in range(1, len(counters)):
		answer += counters[i] * counters[len(counters) - i]
		(counters[i], counters[len(counters) - i]) = (0, 0)
	print(answer)


def func(n, k):
	(q, r) = (n // k, n % k)
	rt = q * (q - 1) // 2 + (k - 1) // 2 * q * q
	if k % 2 == 0:
		if r >= k // 2:
			rt += (k // 2 - 1) * q + q * (q + 1) // 2 + (r - k // 2) * (q + 1)
		else:
			rt += r * q + q * (q - 1) // 2
	elif r >= k // 2:
		rt += k // 2 * q + (r - k // 2) * (q + 1)
	else:
		rt += r * q
	return rt
t = int(input())
for i in range(t):
	(n, k) = (int(a) for a in input().split())
	print(func(n, k))


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	total = 0
	a = N // K + 1
	b = 2 * N // K - (1 if 2 * N % K == 0 else 0)
	if K % 2 == 0:
		total += K * b * (b + 1) // 4 - b
	elif b % 2 == 0:
		total += K * b * (b + 2) // 8 - b // 2
		total += K * b * (b + 2) // 8 - b * (K + 1) // 4
	else:
		total += K * (b - 1) * (b + 1) // 8 - (b - 1) // 2
		total += K * (b + 1) * (b + 3) // 8 - (b + 1) * (K + 1) // 4
	total -= (b - a + 1) * ((a + b) * K - 2 * (N + 1)) // 2
	print(total)


T = int(input())
for i in range(T):
	(N, K) = [int(j) for j in input().split()]
	a = N // K
	b = 2 * N // K
	count = 0
	count += K * a * (a + 1) / 4 - a / 2
	count += N * (b - a) + (b - a) / 2 - K * (b * (b + 1) / 2 - a * (a + 1) / 2) / 2
	if K % 2 == 0:
		count -= b / 2
	else:
		count -= b / 4
	print(round(count))


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	total = 0
	a = N // K + 1
	b = 2 * N // K - (1 if 2 * N % K == 0 else 0)
	if K % 2 == 0:
		total += K * b * (b + 1) // 4 - b
	elif b % 2 == 0:
		total += K * b * (b + 2) // 8 - b // 2
		total += K * b * (b + 2) // 8 - b * (K + 1) // 4
	else:
		total += K * (b - 1) * (b + 1) // 8 - (b - 1) // 2
		total += K * (b + 1) * (b + 3) // 8 - (b + 1) * (K + 1) // 4
	total -= (b - a + 1) * ((a + b) * K - 2 * (N + 1)) // 2
	print(total)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	total = 0
	a = N // K + 1
	b = 2 * N // K - (1 if 2 * N % K == 0 else 0)
	if K % 2 == 0:
		total += K * b * (b + 1) // 4 - b
	elif b % 2 == 0:
		total += K * b * (b + 2) // 8 - b // 2
		total += K * b * (b + 2) // 8 - b * (K + 1) // 4
	else:
		total += K * (b - 1) * (b + 1) // 8 - (b - 1) // 2
		total += K * (b + 1) * (b + 3) // 8 - (b + 1) * (K + 1) // 4
	total -= (b - a + 1) * ((a + b) * K - 2 * (N + 1)) // 2
	print(total)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	total = 0
	a = N // K + 1
	b = 2 * N // K - (1 if 2 * N % K == 0 else 0)
	if K % 2 == 0:
		total += K * b * (b + 1) // 4 - b
	elif b % 2 == 0:
		total += K * b * (b + 2) // 8 - b // 2
		total += K * b * (b + 2) // 8 - b * (K + 1) // 4
	else:
		total += K * (b - 1) * (b + 1) // 8 - (b - 1) // 2
		total += K * (b + 1) * (b + 3) // 8 - (b + 1) * (K + 1) // 4
	total -= (b - a + 1) * ((a + b) * K - 2 * (N + 1)) // 2
	print(total)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	total = 0
	a = N // K + 1
	b = 2 * N // K - (1 if 2 * N % K == 0 else 0)
	if K % 2 == 0:
		total += K * b * (b + 1) // 4 - b
	elif b % 2 == 0:
		total += K * b * (b + 2) // 8 - b // 2
		total += K * b * (b + 2) // 8 - b * (K + 1) // 4
	else:
		total += K * (b - 1) * (b + 1) // 8 - (b - 1) // 2
		total += K * (b + 1) * (b + 3) // 8 - (b + 1) * (K + 1) // 4
	total -= (b - a + 1) * ((a + b) * K - 2 * (N + 1)) // 2
	print(total)


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	R = [n // k for _ in range(k)]
	for i in range(1, n % k + 1):
		R[i] += 1
	b = 1
	e = k - 1
	res = 0
	while b < e:
		if b + e < k:
			b += 1
		elif b + e > k:
			e -= 1
		else:
			res += R[b] * R[e]
			b += 1
			e -= 1
	res += R[0] * (R[0] - 1) // 2
	if b == e:
		res += R[b] * (R[b] - 1) // 2
	print(res)


def sum_sqr(n):
	return n * (n + 1) // 2
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	(num_segs, leftover) = divmod(n, k)
	in_seg_pairs = (k - 1) // 2
	num_pairs = in_seg_pairs * sum_sqr(num_segs) + (k - in_seg_pairs) * sum_sqr(num_segs - 1)
	if leftover <= k // 2:
		num_pairs += leftover * num_segs
	else:
		num_pairs += k // 2 * num_segs + (leftover - k // 2) * (num_segs + 1)
	print(num_pairs)


from math import ceil
T = int(input())
while T:
	(N, K) = [int(elem) for elem in input().split()]
	teliko = 0
	for i in range(1, K // 2 if K % 2 == 0 else K // 2 + 1):
		size1 = (N - i) // K + 1
		size2 = (N - K + i) // K + 1
		teliko += size1 * size2
	size3 = N // K
	teliko += size3 * (size3 - 1) // 2
	if K % 2 == 0:
		size4 = (N - K // 2) // K + 1
		teliko += size4 * (size4 - 1) // 2
	print(teliko)
	T -= 1


def solve():
	s = input()
	(N, K) = s.strip().split(' ')
	N = int(N)
	K = int(K)
	mul = N // K
	X = N - mul * K
	ex = X - K // 2
	if ex < 0:
		ex = 0
	ans = (K - 1) // 2 * mul + mul * (mul - 1) // 2 * K + X * mul + ex
	print(ans)

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


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	total = 0
	a = N // K + 1
	b = 2 * N // K - (1 if 2 * N % K == 0 else 0)
	if K % 2 == 0:
		total += K * b * (b + 1) // 4 - b
	elif b % 2 == 0:
		total += K * b * (b + 2) // 8 - b // 2
		total += K * b * (b + 2) // 8 - b * (K + 1) // 4
	else:
		total += K * (b - 1) * (b + 1) // 8 - (b - 1) // 2
		total += K * (b + 1) * (b + 3) // 8 - (b + 1) * (K + 1) // 4
	total -= (b - a + 1) * ((a + b) * K - 2 * (N + 1)) // 2
	print(total)


def residues_count(N, K, residue):
	return (N - residue) // K + 1
for _ in range(int(input())):
	(N, K) = [int(x) for x in input().strip().split()]
	acc = residues_count(N, K, K) * (residues_count(N, K, K) - 1) // 2
	for residue in range(1, (K + 1) // 2):
		acc += residues_count(N, K, residue) * residues_count(N, K, K - residue)
	if K % 2 == 0:
		acc += residues_count(N, K, K // 2) * (residues_count(N, K, K // 2) - 1) // 2
	print(acc)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	total = 0
	a = N // K + 1
	b = 2 * N // K - (1 if 2 * N % K == 0 else 0)
	if K % 2 == 0:
		total += K * b * (b + 1) // 4 - b
	elif b % 2 == 0:
		total += K * b * (b + 2) // 8 - b // 2
		total += K * b * (b + 2) // 8 - b * (K + 1) // 4
	else:
		total += K * (b - 1) * (b + 1) // 8 - (b - 1) // 2
		total += K * (b + 1) * (b + 3) // 8 - (b + 1) * (K + 1) // 4
	total -= (b - a + 1) * ((a + b) * K - 2 * (N + 1)) // 2
	print(total)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	total = 0
	a = N // K + 1
	b = 2 * N // K - (1 if 2 * N % K == 0 else 0)
	if K % 2 == 0:
		total += K * b * (b + 1) // 4 - b
	elif b % 2 == 0:
		total += K * b * (b + 2) // 8 - b // 2
		total += K * b * (b + 2) // 8 - b * (K + 1) // 4
	else:
		total += K * (b - 1) * (b + 1) // 8 - (b - 1) // 2
		total += K * (b + 1) * (b + 3) // 8 - (b + 1) * (K + 1) // 4
	total -= (b - a + 1) * ((a + b) * K - 2 * (N + 1)) // 2
	print(total)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	total = 0
	a = N // K + 1
	b = 2 * N // K - (1 if 2 * N % K == 0 else 0)
	if K % 2 == 0:
		total += K * b * (b + 1) // 4 - b
	elif b % 2 == 0:
		total += K * b * (b + 2) // 8 - b // 2
		total += K * b * (b + 2) // 8 - b * (K + 1) // 4
	else:
		total += K * (b - 1) * (b + 1) // 8 - (b - 1) // 2
		total += K * (b + 1) * (b + 3) // 8 - (b + 1) * (K + 1) // 4
	total -= (b - a + 1) * ((a + b) * K - 2 * (N + 1)) // 2
	print(total)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	rems = [N // K + (N % K >= i) for i in range(K)]
	rems[0] -= 1
	n = rems[0] * (rems[0] - 1) // 2
	if K % 2 == 0:
		n += rems[K // 2] * (rems[K // 2] - 1) // 2
	n += sum((rems[i] * rems[-i] for i in range(1, K // 2 + K % 2)))
	print(n)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	total = 0
	a = N // K + 1
	b = 2 * N // K - (1 if 2 * N % K == 0 else 0)
	if K % 2 == 0:
		total += K * b * (b + 1) // 4 - b
	elif b % 2 == 0:
		total += K * b * (b + 2) // 8 - b // 2
		total += K * b * (b + 2) // 8 - b * (K + 1) // 4
	else:
		total += K * (b - 1) * (b + 1) // 8 - (b - 1) // 2
		total += K * (b + 1) * (b + 3) // 8 - (b + 1) * (K + 1) // 4
	total -= (b - a + 1) * ((a + b) * K - 2 * (N + 1)) // 2
	print(total)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	total = 0
	a = N // K + 1
	b = 2 * N // K - (1 if 2 * N % K == 0 else 0)
	if K % 2 == 0:
		total += K * b * (b + 1) // 4 - b
	elif b % 2 == 0:
		total += K * b * (b + 2) // 8 - b // 2
		total += K * b * (b + 2) // 8 - b * (K + 1) // 4
	else:
		total += K * (b - 1) * (b + 1) // 8 - (b - 1) // 2
		total += K * (b + 1) * (b + 3) // 8 - (b + 1) * (K + 1) // 4
	total -= (b - a + 1) * ((a + b) * K - 2 * (N + 1)) // 2
	print(total)


T = int(input().strip())
for t in range(T):
	(N, K) = (int(x) for x in input().strip().split(' '))
	NdK = N // K
	NdKph = (2 * N + K) // (2 * K)
	NmK = N % K
	zero = NdK * (NdK - 1) // 2
	half = 0 if K & 1 else NdKph * (NdKph - 1) // 2
	kh = (K - 1) // 2
	if NmK <= kh:
		(M, f) = (NdK, NmK)
	elif not K & 1 and NmK == K // 2:
		(M, f) = (NdK + 1, NmK + 1 - K)
	else:
		(M, f) = (NdK + 1, NmK + 1 - K)
	other = kh * M ** 2 + f * M
	print(zero + half + other)


for test in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	div = int(n / k)
	l = [div]
	near = div * k
	ans = 0
	odd = k & 1
	for i in range(1, k):
		if near + i <= n:
			l.append(div + 1)
		else:
			l.append(div)
	for i in range(1, int(k / 2) + odd):
		ans += l[i] * l[k - i]
	ans += int((l[0] - 1) * l[0] / 2)
	if k % 2 == 0:
		ans += int(l[int(k / 2)] * (l[int(k / 2)] - 1) / 2)
	print(ans)


T = int(input().strip())
for _ in range(T):
	(N, K) = list(map(int, input().strip().split()))
	d = (N + 1) // K
	e = 2 * N // K
	ans = (2 * N + 1) * (e - d) - d + (d * (d + 1) - e * (e + 1) // 2) * K
	print((ans - N * (2 - K % 2) // K) // 2)


T = int(input())
for _ in range(T):
	(N, K) = input().split()
	(N, K) = [int(N), int(K)]
	P = N // K
	R = N % K
	if K & 1:
		print(P * (P - 1) // 2 + K // 2 * P * P + R * P + max(0, R - K // 2))
	else:
		print(P * (P - 1) + (K // 2 - 1) * P * P + R * P + max(0, R - K // 2))


T = int(input())
ans = []
for _ in range(T):
	(N, K) = list(map(int, input().split()))
	total = 0
	a = N // K + 1
	b = 2 * N // K - (1 if 2 * N % K == 0 else 0)
	if K % 2 == 0:
		total += K * b * (b + 1) // 4 - b
	elif b % 2 == 0:
		total += K * b * (b + 2) // 8 - b // 2
		total += K * b * (b + 2) // 8 - b * (K + 1) // 4
	else:
		total += K * (b - 1) * (b + 1) // 8 - (b - 1) // 2
		total += K * (b + 1) * (b + 3) // 8 - (b + 1) * (K + 1) // 4
	total -= (b - a + 1) * ((a + b) * K - 2 * (N + 1)) // 2
	ans.append(total)
for i in range(len(ans)):
	print(ans[i])


t = int(input())
for case in range(t):
	(n, k) = map(int, input().split())
	whole = n // k
	rem = n % k
	i = 1
	j = k - 1
	tot = whole * (whole - 1) // 2
	if k % 2 == 0:
		num = whole + (1 if k // 2 <= rem else 0)
		tot += num * (num - 1) // 2
	while i < j:
		num_i = whole + (1 if i <= rem else 0)
		num_j = whole + (1 if j <= rem else 0)
		tot += num_i * num_j
		i += 1
		j -= 1
	print(tot)


def sumify(b):
	return b * (b + 1) // 2
t = int(input())
for _ in range(t):
	mike = 0
	(n, k) = map(int, input().split(' '))
	q = n // k
	r = n % k
	mike += sumify(q - 1)
	for i in range(1, k // 2 + 1):
		comp = k - i
		if comp != i:
			mike += sumify(q if comp > r else q + 1)
		mike += sumify(q - 1 if i > r else q)
	print(mike)


T = int(input().strip())
for _ in range(T):
	(N, K) = input().strip().split()
	(N, K) = (int(N), int(K))
	ans = 0
	residu = [N // K]
	for i in range(1, K):
		residu.append((N - i) // K + 1)
	for t in range(1, 1 + K // 2):
		if t != K - t:
			ans += residu[t] * residu[K - t]
		else:
			ans += residu[t] * (residu[t] - 1) // 2
	ans += residu[0] * (residu[0] - 1) // 2
	print(ans)


nLines = int(input())
for i in range(nLines):
	elems = input().split()
	N = int(elems[0])
	K = int(elems[1])
	res = 0
	max_elem = int((2 * N + 1) / K)
	first_overlap = int((N + 1) / K) + 1
	n_term = max_elem - first_overlap + 1
	overlap_sum = n_term * (n_term + 1) / 2 * K + n_term * ((first_overlap - 1) * K - N - 1)
	tot_sum = max_elem * (max_elem + 1) / 2 * K / 2 - max_elem
	res = tot_sum - overlap_sum
	if K % 2 == 1:
		res += int((max_elem + 1) / 2) * 1 / 2
	print(int(res))


def solve(N, K):
	s = 0
	if K % 2 == 0:
		for i in range(1, K // 2):
			s += ((N - i) // K + 1) * ((N - (K - i)) // K + 1)
		s += ((N - K // 2) // K + 1) * ((N - K // 2) // K) // 2
		s += ((N - K) // K + 1) * ((N - K) // K) // 2
	else:
		for i in range(1, K // 2 + 1):
			s += ((N - i) // K + 1) * ((N - (K - i)) // K + 1)
		s += ((N - K) // K + 1) * ((N - K) // K) // 2
	return s
T = int(input())
for t0 in range(T):
	(N, K) = (int(a) for a in input().split())
	print(solve(N, K))


t = int(input())
for i in range(t):
	(n, k) = input().strip().split(' ')
	(n, k) = [int(n), int(k)]
	arr = []
	for j in range(k):
		arr.append(0)
	for j in range(k):
		arr[j] = n // k
	for j in range(1, n % k + 1):
		arr[j] += 1
	su = 0
	su += arr[0] * (arr[0] - 1) // 2
	for j in range(1, k // 2 + 1):
		if j != k // 2:
			su += arr[j] * arr[k - j]
		elif k / 2 == k // 2:
			su += arr[j] * (arr[j] - 1) // 2
		else:
			su += arr[j] * arr[k - j]
	print(su)


t = int(input())
for _t in range(t):
	(n, k) = list(map(int, input().strip().split(' ')))
	res = 0
	n_mod_k = n % k
	n_div_k = n // k
	if k % 2 == 1:
		res = n_div_k * (n_div_k - 1) // 2
		if n_mod_k > k // 2:
			res += n_div_k * (n_div_k + 1) * (k - 1 - n_mod_k)
			res += (n_div_k + 1) ** 2 * (n_mod_k - k // 2)
		else:
			res += n_div_k * (n_div_k + 1) * n_mod_k
			res += n_div_k ** 2 * (k // 2 - n_mod_k)
	else:
		res = n_div_k * (n_div_k - 1)
		if n_mod_k >= k // 2:
			res += n_div_k
		if n_mod_k > k // 2:
			res += n_div_k * (n_div_k + 1) * (k - 1 - n_mod_k)
			res += (n_div_k + 1) ** 2 * (n_mod_k - k // 2)
		else:
			if n_mod_k == k // 2:
				n_mod_k -= 1
			res += n_div_k * (n_div_k + 1) * n_mod_k
			res += n_div_k ** 2 * (k // 2 - 1 - n_mod_k)
	print(res)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	q = n % k - k // 2 - 1
	m = n // k
	s = m * (m + 1) * k // 2
	if q < 0:
		s += q * m
	else:
		s += (q + 1) * (m + 1) - m
	print(s)


t = int(input())
while t > 0:
	t -= 1
	(n, k) = [int(x) for x in input().split()]
	q = n // k
	r = n % k
	classes = [q for i in range(k)]
	for i in range(1, r + 1):
		classes[i] += 1
	ret = 0
	head = 1
	tail = k - 1
	while head < tail:
		ret += classes[head] * classes[tail]
		head += 1
		tail -= 1
	ret += classes[0] * (classes[0] - 1) // 2
	if k & 1 == 0 and k >> 1 <= n:
		ret += classes[k >> 1] * (classes[k >> 1] - 1) // 2
	print(ret)


T = int(input())
for t in range(T):
	(N, K) = map(int, input().split())
	x = N // K
	count = x * (x - 1) // 2
	if K & 1 == 0:
		i = K // 2
		x = (N + i) // K
		count += x * (x - 1) // 2
	for i in range(1, (K + 1) // 2):
		x = (N + K - i) // K
		y = (N + i) // K
		count += x * y
	print(count)


def noPairs(k, N):
	if k <= N + 1:
		if k % 2 == 0:
			return (k - 1) // 2
		return k // 2
	else:
		return noPairs(k - 2 * (k - N - 1), N)
for _ in range(int(input())):
	(N, K) = list(map(int, input().split()))
	if K % 2 == 0:
		fn = noPairs(K, N)
		ln = noPairs(N - N % K, N)
		sln = noPairs(N + K - N % K, N)
		d1 = N // K
		d2 = (sln + (K // 2 - sln % (K // 2))) // (K // 2)
		t = int((fn + ln) * d1 / 2) + int((2 * sln - K // 2 * (d2 - 1)) * (d2 / 2))
	else:
		fn = 2 * noPairs(K, N) + K // 2
		d = N // K // 2
		t = int((2 * fn + (d - 1) * 2 * K) * (d / 2))
		if N // K % 2 != 0:
			t += noPairs(N - N % K, N)
		v = N + K - N % K
		while v < 2 * N:
			t += noPairs(v, N)
			v += K
	print(t)


T = int(input())
for run in range(T):
	(n, k) = [int(i) for i in input().split()]
	total = 0
	for i in range(k):
		pair = (k - i) % k
		if pair < i:
			break
		count = n // k
		if 1 <= i <= n % k:
			count += 1
		if pair == i:
			total += (count - 1) * count // 2
		else:
			pc = n // k
			if 1 <= pair <= n % k:
				pc += 1
			total += count * pc
	print(total)


import math
t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	b1 = (n - n % k) // k
	n12 = b1 // 2
	n11 = b1 - n12
	a11 = math.ceil(k / 2) - 1
	d1 = math.ceil(3 * k / 2) - 1 - a11
	a12 = k - 1
	l = n + (k - n % k)
	s11 = n11 * (2 * a11 + (n11 - 1) * d1) // 2
	s12 = n12 * (2 * a12 + (n12 - 1) * d1) // 2
	b2 = (n + n - 1) // k - n11 - n12
	a21 = math.ceil(l / 2) - l + n
	a22 = math.ceil((l + k) / 2) - l - k + n
	d2 = math.ceil((l + 2 * k) / 2) - l - 2 * k + n - a21
	n22 = b2 // 2
	n21 = b2 - n22
	s21 = n21 * (2 * a21 + (n21 - 1) * d2) // 2
	s22 = n22 * (2 * a22 + (n22 - 1) * d2) // 2
	print(s11 + s12 + s21 + s22)


import math
t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	b1 = (n - n % k) // k
	n12 = b1 // 2
	n11 = b1 - n12
	a11 = math.ceil(k / 2) - 1
	d1 = math.ceil(3 * k / 2) - 1 - a11
	a12 = k - 1
	l = n + (k - n % k)
	s11 = n11 * (2 * a11 + (n11 - 1) * d1) // 2
	s12 = n12 * (2 * a12 + (n12 - 1) * d1) // 2
	b2 = (n + n - 1) // k - n11 - n12
	a21 = math.ceil(l / 2) - l + n
	a22 = math.ceil((l + k) / 2) - l - k + n
	d2 = math.ceil((l + 2 * k) / 2) - l - 2 * k + n - a21
	n22 = b2 // 2
	n21 = b2 - n22
	s21 = n21 * (2 * a21 + (n21 - 1) * d2) // 2
	s22 = n22 * (2 * a22 + (n22 - 1) * d2) // 2
	print(s11 + s12 + s21 + s22)


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	no_of_block = n // k
	if k % 2 == 0:
		pair_in_block = k // 2 - 1
		if n % k == 0:
			exact_divisors = no_of_block * (no_of_block - 1)
			buffer = 0
		elif n % k < k // 2:
			x = n % k
			buffer = x * no_of_block
			exact_divisors = no_of_block * (no_of_block - 1)
		elif n % k == k // 2:
			x = n % k - 1
			buffer = x * no_of_block
			exact_divisors = no_of_block * (no_of_block - 1) // 2 + (no_of_block + 1) * no_of_block // 2
		else:
			x = k // 2 - 1
			y = n % k - k // 2
			buffer = x * no_of_block + y * no_of_block + y
			exact_divisors = no_of_block * (no_of_block - 1) // 2 + (no_of_block + 1) * no_of_block // 2
	else:
		pair_in_block = k // 2
		exact_divisors = no_of_block * (no_of_block - 1) // 2
		if n % k == 0:
			buffer = 0
		else:
			x = n % k
			y = n % k - k // 2
			buffer = k // 2 * no_of_block + y * no_of_block + y if x > k // 2 else x * no_of_block
	common_part = pair_in_block * no_of_block * no_of_block
	print(common_part + buffer + exact_divisors)


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	perfect = n // k
	res = 0
	res += (perfect - 1) * k * perfect // 2 + perfect * ((k - 1) // 2)
	left = n % k
	res += perfect * left
	res += max(0, left - k // 2)
	print(res)


T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	n_rem = [N // K] * K
	for i in range(N % K):
		n_rem[i + 1] += 1
	res = n_rem[0] * (n_rem[0] - 1) // 2
	if K % 2 == 0:
		for i in range(1, K // 2):
			res += n_rem[i] * n_rem[K - i]
		res += n_rem[K // 2] * (n_rem[K // 2] - 1) // 2
	else:
		for i in range(1, (K + 1) // 2):
			res += n_rem[i] * n_rem[K - i]
	print(res)


from math import factorial as fa
t = int(input())
for i in range(t):
	(n, k) = [int(i) for i in input().split()]
	p = n % k
	z = n // k
	a = [z] * k
	a[0] = z
	sum = 0
	for i in range(1, p + 1):
		a[i] = a[i] + 1
	for i in range(1, k):
		if i <= (k - 1) // 2:
			sum = sum + a[i] * a[k - i]
	if k - 1 & 1:
		sum = sum + a[k // 2] * (a[k // 2] - 1) // 2
	sum = sum + a[0] * (a[0] - 1) // 2
	print(sum)


T = int(input())
for case in range(T):
	(N, K) = input().split(' ')
	(K, N) = [int(K), int(N)]
	times = N // K
	rem = N % K
	if 2 * rem > K:
		times = times + 1
		rem = -K + rem
	summa = 0
	if K % 2 == 0:
		even = True
	else:
		even = False
	if even:
		summa += times * times * (K - 2) / 2 + times * (times - 1)
		if rem < 0:
			summa += rem * times + 1
		else:
			summa += rem * times
	else:
		summa += times * times * (K - 1) / 2 + times * (times - 1) / 2
		if rem < 0:
			summa += rem * times + 1
		else:
			summa += rem * times
	print(int(summa))


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	total = 0
	a = N // K + 1
	b = 2 * N // K - (1 if 2 * N % K == 0 else 0)
	if K % 2 == 0:
		total += K * b * (b + 1) // 4 - b
	elif b % 2 == 0:
		total += K * b * (b + 2) // 8 - b // 2
		total += K * b * (b + 2) // 8 - b * (K + 1) // 4
	else:
		total += K * (b - 1) * (b + 1) // 8 - (b - 1) // 2
		total += K * (b + 1) * (b + 3) // 8 - (b + 1) * (K + 1) // 4
	total -= (b - a + 1) * ((a + b) * K - 2 * (N + 1)) // 2
	print(total)


import sys
import math

def divSums(n, k):
	count = 0
	for x in range(1, n + 1):
		count2 = 0
		for y in range(x + 1, n + 1):
			if (x + y) % k == 0:
				count += 1
				count2 += 1
		print(repr(x) + ' ' + repr(count2))
	return count

def divSums2(n, k):
	count = 0
	for x in range(1, n + 1):
		k2 = k / 2
		i = int(k2 * int(x / k2) - x % k2)
		ad = (n - i) // k
		count += ad
		print(repr(x) + ' ' + repr(ad))
	return count

def divSums3(n, k):
	count = 0
	for x in range(1, k + 1):
		k2 = k / 2
		i = int(k2 * int(x / k2) - x % k2)
		ad = (n - i) // k
		count += int(ad * (ad + 1) / 2)
	return count
T = int(input().strip())
for a0 in range(T):
	a = [int(a_temp) for a_temp in input().strip().split(' ')]
	print(divSums3(a[0], a[1]))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	(q, r) = divmod(n, k)
	m = k // 2
	if k & 1:
		c = q * (q - 1) // 2
	else:
		if r < m:
			c = q * (q - 1)
		else:
			c = q * q
			r -= 1
		k -= 1
		m -= 1
	if r <= m:
		c += r * q * (q + 1) + (m - r) * q * q
	else:
		c += (r - m) * (q + 1) * (q + 1) + (k - r - 1) * q * (q + 1)
	print(c)


T = int(input())
for t in range(T):
	(N, K) = map(int, input().split())
	A = [1 + (N - k) // K for k in range(K)]
	A[0] -= 1
	ans = A[0] * (A[0] - 1) // 2
	if K % 2 == 0:
		ans += A[K // 2] * (A[K // 2] - 1) // 2
	for i in range(1, (K + 1) // 2):
		ans += A[i] * A[K - i]
	print(ans)


import math
for _ in range(int(input())):
	(n, d) = [int(temp) for temp in input().split()]
	loop = n // d
	r = n % d
	pair = d * (loop - 1) * loop // 2 + (r + (d - 1) // 2) * loop
	if r > d // 2:
		pair += r - d // 2
	print(pair)


for _ in range(int(input())):
	(n, d) = [int(temp) for temp in input().split()]
	loop = n // d
	r = n % d
	pair = d * (loop - 1) * loop // 2 + (r + (d - 1) // 2) * loop
	if r > d // 2:
		pair += r - d // 2
	print(pair)


for _ in range(int(input())):
	(n, d) = [int(temp) for temp in input().split()]
	loop = n // d
	r = n % d
	pair = d * (loop - 1) * loop // 2 + (r + (d - 1) // 2) * loop
	if r > d // 2:
		pair += r - d // 2
	print(pair)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	x = n // k
	r = n % k
	p = k * (x - 1) * x // 2 + (r + (k - 1) // 2) * x
	if r > k // 2:
		p += r - k // 2
	print(p)


for _ in range(int(input())):
	(n, d) = [int(temp) for temp in input().split()]
	loop = n // d
	r = n % d
	pair = d * (loop - 1) * loop // 2 + (r + (d - 1) // 2) * loop
	if r > d // 2:
		pair += r - d // 2
	print(pair)


def cnt_mod(N, K, k):
	k = (k - 1) % K
	return N // K + int(k < N % K)

def main():
	T = int(input())
	for _ in range(T):
		(N, K) = map(int, input().split())
		C = 0
		for k in range(K // 2 + 1):
			if 2 * k % K == 0:
				c = cnt_mod(N, K, k)
				C += c * (c - 1) // 2
			else:
				C += cnt_mod(N, K, k) * cnt_mod(N, K, K - k)
		print(C)
main()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	(q, r) = divmod(n, k)
	pair = k * (q - 1) * q // 2 + (r + (k - 1) // 2) * q
	if r > k // 2:
		pair += r - k // 2
	print(pair)


from math import ceil, floor
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	(a, b) = divmod(n, k)
	num1 = ceil(k / 2 - 1)
	num2 = k - num1
	addition1 = a * (a + 1) // 2
	addition2 = addition1 - a
	t_addition1 = addition1 * num1
	t_addition2 = addition2 * num2
	(extra1, extra2) = (0, 0)
	if b != 0:
		extra1 = b * a
	if b > floor(k / 2):
		extra2 = b - floor(k / 2)
	print(t_addition1 + t_addition2 + extra1 + extra2)


import sys

def solve(N, K):
	L = N // K
	R = N % K
	dic = {}
	for i in range(K):
		dic[i] = L
	for i in range(1, R + 1):
		dic[i] += 1
	total = 0
	for i in range(K):
		j = (K - i) % K
		if i > j:
			break
		if i == j:
			total += dic[i] * (dic[i] - 1) // 2
		else:
			total += dic[i] * dic[j]
	return total
T = int(input())
for t in range(T):
	(N, K) = [int(x) for x in input().split(' ')]
	print(solve(N, K))


for _ in range(int(input())):
	(n, d) = [int(temp) for temp in input().split()]
	loop = n // d
	r = n % d
	pair = d * (loop - 1) * loop // 2 + (r + (d - 1) // 2) * loop
	if r > d // 2:
		pair += r - d // 2
	print(pair)


for _ in range(int(input())):
	(n, d) = [int(temp) for temp in input().split()]
	loop = n // d
	r = n % d
	pair = d * (loop - 1) * loop // 2 + (r + (d - 1) // 2) * loop
	if r > d // 2:
		pair += r - d // 2
	print(pair)


import os
import sys
for _ in range(int(input())):
	(n, d) = [int(temp) for temp in input().split()]
	loop = n // d
	r = n % d
	pair = d * (loop - 1) * loop // 2 + (r + (d - 1) // 2) * loop
	if r > d // 2:
		pair += r - d // 2
	print(pair)


t = int(input())
for te in range(t):
	(n, k) = list(map(int, input().split()))
	dp = [n // k for i in range(k)]
	ans = 0
	for i in range(1, n % k + 1):
		dp[i] += 1
	for i in range(k):
		a = dp[i]
		if i > k // 2:
			ans += a * (a + 1) // 2
		else:
			ans += a * (a - 1) // 2
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	cnt = [n // k] * k
	for i in range(1, n % k + 1):
		cnt[i] += 1
	ans = 0
	ans += cnt[0] * (cnt[0] - 1) // 2
	for i in range(1, k // 2):
		ans += cnt[i] * cnt[k - i]
	if k % 2 == 0:
		ans += cnt[k // 2] * (cnt[k // 2] - 1) // 2
	else:
		ans += cnt[k // 2] * cnt[k // 2 + 1]
	print(ans)


import sys
from time import time

def solve_bf(n, k):
	print('n=%d k=%d' % (n, k), file=sys.stderr)
	sm = 0
	for i in range(1, n + 1):
		for j in range(i + 1, n + 1):
			if (i + j) % k == 0:
				sm += 1
	return sm

def matches(n, k):
	if k <= n:
		return (k + 1) // 2
	return (2 * n - k + 1) // 2

def solve_bf2(n, k):
	print('n=%d k=%d' % (n, k), file=sys.stderr)
	sm = 0
	for i in range(k, 2 * n, k * 2):
		m = matches(n, i)
		sm += m
		print('%d' % matches(n, i), end=' ', file=sys.stderr)
	print(file=sys.stderr)
	for i in range(k + k, 2 * n, k * 2):
		m = matches(n, i)
		sm += m
		print('%d' % matches(n, i), end=' ', file=sys.stderr)
	print(file=sys.stderr)
	sm -= n // k
	return sm

def solve(n, k):
	N = 2 * n - 1
	vv = list(((k * (1 + i) + 1) // 2 for i in range(4)))
	d = vv[2] - vv[0]
	(fr1, fr2) = vv[:2]
	l = n // k
	l2 = l // 2
	l1 = l - l2
	u1 = (fr1 + fr1 + (l1 - 1) * d) * l1 // 2
	u2 = (fr2 + fr2 + (l2 - 1) * d) * l2 // 2
	total = u1 + u2
	vv = list(((2 * n - k * (l + 1 + i) + 1) // 2 for i in range(3)))
	d = vv[2] - vv[0]
	u = (2 * n - 1) // k - l
	b = u // 2
	a = u - b
	if l1 > l2:
		(l2, l1) = (a, b)
		(fr2, fr1) = vv[:2]
	else:
		(l1, l2) = (a, b)
		(fr1, fr2) = vv[:2]
	u1 = (fr1 + fr1 + (l1 - 1) * d) * l1 // 2
	u2 = (fr2 + fr2 + (l2 - 1) * d) * l2 // 2
	total += u1 + u2
	total -= n // k
	return total
tm = time()
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	print(solve(n, k))
print('time elapsed: %s' % (time() - tm,), file=sys.stderr)