Chef is playing a game with two of his friends. In this game, each player chooses an integer between $1$ and $P$ inclusive. Let's denote the integers chosen by Chef, friend 1 and friend 2 by $i$, $j$ and $k$ respectively; then,  Chef's score is
(((Nmodi)modj)modk)modN.(((Nmodi)modj)modk)modN.(((N\,\mathrm{mod}\,i)\,\mathrm{mod}\,j)\,\mathrm{mod}\,k)\,\mathrm{mod}\,N\,.

Chef wants to obtain the maximum possible score. Let's denote this maximum score by $M$. Find the number of ways to choose the triple $(i,j,k)$ so that Chef's score is equal to $M$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains two space-separated integers $N$ and $P$.

-----Output-----
For each test case, print a single line containing one integer — the number of ways to obtain the maximum score.

-----Constraints-----
- $1 \le T \le 10^6$
- $1 \le N \le P \le 10^6$

-----Subtasks-----
Subtask #1 (10 points):
- $1 \le T \le 100$
- $1 \le N \le P \le 100$
Subtask #2 (90 points): original constraints

-----Example Input-----
2
4 4
3 4

-----Example Output-----
9
13

-----Explanation-----
Example case 1: Chef's maximum possible score is $M = 1$. All possible values of $(i, j, k)$ such that the score is $1$ are
$(3, 2, 2)$,
$(3, 2, 3)$,
$(3, 2, 4)$,
$(3, 3, 2)$,
$(3, 3, 3)$,
$(3, 3, 4)$,
$(3, 4, 2)$,
$(3, 4, 3)$,
$(3, 4, 4)$.

Difficulty: MEDIUM_HARD
Tags: Combinatorics

Mathematics

Starter code:

Solutions:
R = lambda : map(int, input().split())
t = int(input())
for _ in range(t):
	(n, p) = R()
	max_no = n - (int(n / 2) + 1)
	if max_no == 0:
		print(p * p * p)
	else:
		ans = 1 * (p - max_no) * (p - max_no) + (p - n) * (p - max_no) + (p - n) * (p - n)
		print(ans)


from math import ceil
t = int(input())
for i in range(t):
	l = list(map(int, input().split()))
	n = l[0]
	p = l[1]
	if n == 1 or n == 2:
		print(p ** 3)
		continue
	m = ceil(n / 2 - 1)
	s = (p - m) ** 2 + (p - n) ** 2 + (p - n) * (p - m)
	print(s)


t = int(input())
mod_i = list()
mod_n = list()
for i in range(0, t):
	value = list(map(int, input().split()))
	(n, p) = (value[0], value[1])
	m = n % (n // 2 + 1)
	if m == 0:
		count = p * p * p
	else:
		count = (p - m) * (p - m) + (p - n) * (p - m + (p - n))
	print(count)


t = int(input())
for _ in range(t):
	(n, p) = map(int, input().split())
	if n <= 2:
		print(p ** 3)
	else:
		m = (n - 1) // 2
		count = 0
		count += 1 * (p - m) * (p - m)
		count += (p - n) * 1 * (p - m)
		count += (p - n) * (p - n) * 1
		print(count)


test_cases_count = int(input())
for test_case_id in range(1, test_cases_count + 1):
	(N, P) = map(int, input().split())
	if N <= 2:
		res = P ** 3
	else:
		highest_mod = (N - 1) // 2
		res = (P - highest_mod) ** 2 + (P - N) * (P - highest_mod) + (P - N) ** 2
	print(res)


try:
	t = int(input())
	for i in range(t):
		l = list(map(int, input().split()))
		n = l[0]
		p = l[1]
		if n == 1 or n == 2:
			print(p ** 3)
		elif n % 2 == 0:
			print((p - (n // 2 - 1)) ** 2 + (p - n) * (p - (n // 2 - 1)) + (p - n) ** 2)
		else:
			print((p - n // 2) ** 2 + (p - n) * (p - n // 2) + (p - n) ** 2)
except Exception:
	pass


def check(n, p, divisor):
	product = 1
	if p > n:
		i = p - n
		j = p - n
		k = 1
		product = i * j
		i = 1
		j = p - n % divisor
		k = j
		product += i * j * k
		i = p - n
		j = 1
		k = p - n % divisor
		product += i * j * k
		print(product)
	elif p <= n and p >= divisor:
		i = 1
		j = p - n % divisor
		k = j
		product = i * j * k
		print(product)
	elif p < divisor:
		greatest = 0
		for m in range(1, p):
			if n % m > greatest:
				greatest = n % m
		i = 1
		j = p - greatest
		k = p - greatest
		product = i * j * k
		print(product)
t = int(input())
while t > 0:
	(n, p) = tuple(map(int, input().split()))
	if n <= 2:
		print(p * p * p)
	elif n % 2 == 0:
		check(n, p, n // 2 + 1)
	else:
		check(n, p, (n + 1) // 2)
	t -= 1


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


def main():
	for i in range(int(input())):
		(n, p) = map(int, input().split())
		m = n % (n // 2 + 1)
		if m == 0:
			print(p * p * p)
		else:
			c1 = p - n
			t1 = c1 * c1
			t2 = c1 * (p - m)
			t3 = (p - m) * (p - m)
			cases = t1 + t2 + t3
			print(cases)
main()


t = int(input())
for i in range(t):
	l = input().split()
	n = int(l[0])
	p = int(l[1])
	if n == 1:
		ans = p ** 3
	elif n == 2:
		ans = p ** 3
	elif p <= n // 2:
		ans = 0
	elif p <= n:
		ans = (p - n % (n // 2 + 1)) ** 2
	elif n % 2 == 1:
		ans = (p - n % (n // 2 + 1)) ** 2 + (p - n) * (2 * p - n - (n - 1) // 2)
	else:
		ans = (p - n % (n // 2 + 1)) ** 2 + (p - n) * (2 * p - n - n // 2 + 1)
	print(ans)


t = int(input())
for i in range(t):
	l = list(map(int, input().split(' ')))
	(n, p) = (l[0], l[1])
	m = n % (n // 2 + 1)
	if m == 0:
		res = p ** 3
	else:
		res = (p - m) ** 2 + (p - n) * (p - m) + (p - n) ** 2
	print(res)


t = int(input())
while t > 0:
	temp = input()
	n = int(temp.split(' ')[0])
	p = int(temp.split(' ')[1])
	i = int()
	sum = 0
	if n % 2 == 0:
		i = n // 2 + 1
	else:
		i = (n + 1) // 2
	if n > 2:
		sum = (p - n % i) ** 2 + (p - n) * (p - n % i) + (p - n) ** 2
	else:
		sum = p ** 3
	print(sum)
	t = t - 1


cases = int(input())
for case in range(cases):
	(n, p) = [int(i) for i in input().split()]
	if n < 3:
		print(p * p * p)
	else:
		m = n // 2 + 1
		r = n % m
		a = (p - r) * (p - r)
		b = (p - r) * (p - n)
		c = (p - n) * (p - n)
		print(a + b + c)


for _ in range(int(input())):
	(n, p) = input().split()
	n = int(n)
	p = int(p)
	if n <= 2:
		print(p ** 3)
	else:
		best = n // 2 + 1
		print((p - n % best) ** 2 + (p - n) * (p - n % best) + (p - n) ** 2)


import math
t = int(input())
for _ in range(t):
	(n, p) = map(int, input().split())
	idx = 1
	maxMod = math.floor((n - 1) / 2)
	comb = 0
	comb += (p - maxMod) ** 2
	comb += (p - n) * (p - maxMod)
	comb += (p - n) * (p - n)
	if n <= 2:
		print(p * p * p)
	else:
		print(comb)


t = int(input())
while t:
	t = t - 1
	(n, p) = list(map(int, input().split()))
	max_remainder = n - (int(n / 2) + 1)
	if max_remainder == 0:
		print(p * p * p)
	else:
		a = p - max_remainder
		b = p - n
		ans = a ** 2 + b * (a + b)
		print(ans)


from sys import stdin, stdout
l_in = stdin.readline
l_out = stdout.write
t = int(l_in())
for i in range(t):
	MaxM = 0
	count = 0
	(N, P) = list(map(int, l_in().strip().split()))
	ar = list(range(1, P + 1))
	for i in ar:
		for j in ar:
			for k in ar:
				M = N % i % j % k % N
				if M > MaxM:
					count = 1
					MaxM = M
				elif M == MaxM:
					count = count + 1
	print(count)


for __ in range(int(input())):
	(k, p) = map(int, input().split())
	d = k % (k // 2 + 1)
	if d == 0:
		t = p * p * p
	else:
		t = (p - d) * (p - d) + (p - d) * (p - k) + (p - k) * (p - k)
	print(t)


tt = int(input())
for i in range(tt):
	x = input().split()
	n = int(x[0])
	p = int(x[1])
	max = 0
	s = 0
	if n <= 2:
		print(p * p * p)
	else:
		max = int((n - 1) / 2)
		a1 = p - n
		a2 = p - max
		ss = a1 * a1 + a2 * a2 + a1 * a2
		print(ss)


from math import ceil
t = int(input())
for zz in range(t):
	(n, p) = map(int, input().split())
	if n == 1 or n == 2:
		print(p * p * p)
		continue
	m = ceil(n / 2) - 1
	x = p - m
	s = x * x
	s = s + (p - n) * (p - m + p - n)
	print(s)


t = int(input())
while t > 0:
	t -= 1
	(n, p) = [int(x) for x in input().split()]
	if n > 3 and p > 3:
		if n == p:
			print((n // 2 + 1) ** 2)
		else:
			if n % 2 == 1:
				tem = (n - 5) // 2
			else:
				tem = (n - 4) // 2
			rem = p - n - 1
			toko = 21 + tem * tem + 9 * tem + 3 * rem * (5 + tem + rem)
			print(toko)
	elif n == 3 and p == 3:
		print(4)
	elif n == 1 or n == 2:
		print(p ** 3)
	elif n == 3 and p > 3:
		if p == 4:
			print(13)
		else:
			tem1 = 13
			tem2 = 15
			for i in range(1, p - n):
				tem1 += tem2
				tem2 += 6
			print(tem1)


for _ in range(int(input())):
	(n, p) = map(int, input().split())
	m = n % (n // 2 + 1)
	if m == 0:
		ans = p * p * p
	else:
		ans = (p - n) * (2 * p - (m + n))
		ans += (p - m) * (p - m)
	print(ans)


def my_func(n, p):
	sum = 0
	if n <= 2:
		print(p ** 3)
	else:
		k = p - n % (n // 2 + 1)
		sum += k ** 2
		if n < p:
			sum += (p - n) ** 2 + (p - n) * k
		print(sum)
t = int(input())
for i in range(t):
	(n, p) = [int(x) for x in input().split()]
	my_func(n, p)


t = int(input())
for _ in range(t):
	np = list(map(int, input().split()))
	n = np[0]
	p = np[1]
	if n == 2:
		rem = 0
	elif n % 2 == 0:
		div = n // 2 + 1
		rem = n // 2 - 1
	elif n % 2 != 0:
		div = n // 2 + 1
		rem = n // 2
	if rem != 0:
		print((p - rem) * (p - rem) + (p - n) * (p - rem) + (p - n) * (p - n))
	else:
		print(p * p * p)


test = int(input())
while test > 0:
	(num, p) = map(int, input().split())
	aa = num // 2 + 1
	if num == 1 or num == 2:
		print(p * p * p)
	else:
		aa = num % aa
		b = (p - aa) ** 2
		c = (p - num) * (p - aa)
		a = (p - num) * (p - num)
		print(b + c + a)
	test = test - 1


n = int(input())
mod = 0
while n != 0:
	(a, b) = input().split(' ')
	a = int(a)
	b = int(b)
	mod = int(a / 2) + 1
	mod = a - mod
	dist = (b - mod) * (b - mod) + (b - mod) * (b - a) + (b - a) * (b - a)
	if a < 3:
		print(b ** 3)
	else:
		print(int(dist))
	n = n - 1


t = int(input())
while t:
	(n, p) = input().split()
	n = int(n)
	p = int(p)
	max = n % (n // 2 + 1)
	if max == 0:
		r = p * p * p
	else:
		r = (p - max) * (p - max) + (p - n) * (p - max) + (p - n) * (p - n)
	print(r)
	t -= 1


for _ in range(int(input())):
	(n, p) = map(int, input().split())
	d = n % (n // 2 + 1)
	if n == 2 or n == 1:
		t = p * p * p
	else:
		t = (p - d) * (p - d) + (p - d) * (p - n) + (p - n) * (p - n)
	print(t)


t = int(input())
for _ in range(t):
	(n, p) = map(int, input().strip().split())
	if n <= 2:
		print(p * p * p)
	else:
		m = (n - 1) // 2
		res = (p - m) ** 2 + (p - n) ** 2 + (p - m) * (p - n)
		print(res)


t = int(input())
while t > 0:
	a = []
	a = input().split()
	n = int(a[0])
	p = int(a[1])
	d = n // 2
	l = n % (d + 1)
	if l == 0:
		print(p * p * p)
	else:
		print((p - l) * (p - l) + (p - n) * (p - l + (p - n)))
	t = t - 1


t = int(input())
for i in range(t):
	a = list(map(int, input().split(' ')))
	if a[0] < 3:
		m = a[1] ** 3
	else:
		s = int(a[0] / 2) + 1
		if a[1] >= s:
			w = a[0] % s
			m = (a[1] - w) ** 2
			if a[0] < a[1]:
				m = m + (a[1] - a[0]) ** 2
			if a[0] < a[1]:
				m = m + (a[1] - a[0]) * (a[1] - w)
		else:
			kl = []
			for i in range(1, a[1] + 1):
				rr = a[0] % i
				if i == 0:
					mr = rr
					kl.append(i)
				elif rr > mr:
					mr = rr
					kl = []
					kl.append(i)
				elif rr == mr:
					kl.append(i)
			m = (a[1] - mr) ** 2 * len(kl)
	print(m)


import math
t = int(input())
for i in range(t):
	(n, p) = list(map(int, input().split()))
	maxMod = int(n / 2 + 1)
	tmp = n % maxMod
	if maxMod == 1 or n == 2 or n == 1:
		print(p ** 3)
	else:
		print((p - n) * (p - tmp) + (p - n) * (p - n) + (p - tmp) * (p - tmp))


for _ in range(int(input())):
	(n, p) = map(int, input().split())
	divis = n // 2 + 1
	maxi = n % divis
	if maxi == 1:
		i = p - 1
		a = i ** 2
		j = (p - n) * (p - 1 + (p - n))
		a += j
	else:
		i = p - maxi
		a = i ** 2
		j = (p - n) * (p - n + i)
		a += j
	if maxi == 0:
		a = p * p * p
	print(a)


test_cases = int(input())
while test_cases > 0:
	(n, p) = map(int, input().split(' '))
	count = 0
	if n != 1 and n != 2:
		p += 1
		k = j = i = n // 2 + 1
		if n % 2 == 0:
			k = j = i = n // 2
			i += 1
		count = (p - j) * (p - k)
		count += (p - (n + 1)) * (p - k)
		count += (p - (n + 1)) ** 2
	else:
		count = p ** 3
	print(count)
	test_cases -= 1


T = int(input())
for i in range(T):
	(N, P) = map(int, input().split())
	req = N // 2 + 1
	if N == 1 or N == 2:
		print(P ** 3)
	else:
		req = N % req
		b = (P - req) ** 2
		c = (P - N) * (P - req)
		a = (P - N) * (P - N)
		print(a + b + c)


from sys import stdin
t = int(stdin.readline())
while t:
	(n, p) = [int(x) for x in stdin.readline().split()]
	l_rem = n % (n // 2 + 1)
	if l_rem == 0:
		print(p * p * p)
	else:
		ans = (p - l_rem) * (p - l_rem)
		ans += (p - n) * (p - l_rem)
		ans += (p - n) * (p - n)
		print(ans)
	t -= 1


n = int(input())
for i in range(n):
	a = list(map(int, input().split()))
	if a[0] == 2 or a[0] == 1:
		ans = a[1] ** 3
		print(ans)
	else:
		l = a[0]
		s = l // 2 + 1
		t = l % s
		y = a[1] - t
		r = y ** 2
		g = 0
		if a[1] > a[0]:
			f = a[1] - a[0]
			g = f * y + f * f
		ans = g + r
		print(ans)


T = int(input())
while T > 0:
	(n, p) = input().split()
	n = int(n)
	p = int(p)
	if n > 2:
		Rem = n % (n // 2 + 1)
		total = (p - Rem) * (p - Rem) + (p - n) * (p - Rem) + (p - n) * (p - n)
	else:
		total = p * p * p
	print(total)
	T = T - 1


t = int(input())
for i in range(t):
	inp = list(map(int, input().split()))
	n = inp[0]
	p = inp[1]
	if n == 1 or n == 2:
		print(p * p * p)
	elif n % 2 == 0:
		print((p - (n // 2 - 1)) ** 2 + (p - n) * (p - (n // 2 - 1)) + (p - n) ** 2)
	else:
		print((p - (n - 1) // 2) ** 2 + (p - n) * (p - (n - 1) // 2) + (p - n) ** 2)


for __ in range(int(input())):
	(n, p) = map(int, input().split())
	d = n % (n // 2 + 1)
	if d == 0:
		test = p * p * p
	else:
		test = (p - d) * (p - d) + (p - d) * (p - n) + (p - n) * (p - n)
	print(test)


t = int(input())
while t:
	t -= 1
	(n, p) = map(int, input().split())
	x = n // 2 + 1
	x = n % x
	if x == 0:
		print(p * p * p)
	else:
		print((p - x) * (p - x) + (p - x) * (p - n) + (p - n) * (p - n))


for i in range(int(input())):
	(n, p) = map(int, input().split())
	b = n // 2 + 1
	x = n % b
	c1 = p - x
	c2 = p - n
	if x == 0:
		print(p ** 3)
	else:
		r1 = c1 ** 2 + c2 * c1 + c2 ** 2
		print(r1)


t = int(input())
while t:
	(n, p) = map(int, input().split())
	if n <= 2:
		print(p * p * p)
	else:
		max = int((n - 1) / 2)
		c = (p - max) * (p - max)
		c = c + (p - n) * (p - max)
		c = c + (p - n) * (p - n)
		print(c)
	t = t - 1


t = int(input())
for k in range(0, t):
	(n, p) = input().split()
	(n, p) = [int(n), int(p)]
	if n <= 2:
		print(p ** 3)
	else:
		c = (p - n) * (p - n)
		c += (p - n) * (p - (n - 1) // 2)
		c += (p - (n - 1) // 2) * (p - (n - 1) // 2)
		print(c)


t = int(input())
for test in range(t):
	(n, p) = map(int, input().split())
	m = round(n / 2 - 0.7)
	if m == 0:
		choices = p ** 3
	else:
		choices = (p - m) ** 2 + (p - n) ** 2 + (p - m) * (p - n)
	print(choices)


for _ in range(0, int(input())):
	(n, p) = map(int, input().split())
	if n == 1 or n == 2:
		print(int(pow(p, 3)))
	elif n == p:
		print(int(pow(int(p / 2) + 1, 2)))
	else:
		m = int((n - 1) / 2)
		b = p - m
		c = p - n
		print(int(pow(b, 2) + pow(c, 2) + b * c))


for _ in range(int(input())):
	(n, p) = map(int, input().split())
	max_mod = n % (n // 2 + 1)
	if max_mod == 0:
		print(p * p * p)
	else:
		print((p - max_mod) ** 2 + (p - max_mod) * (p - n) + (p - n) ** 2)


for T in range(int(input())):
	(N, P) = map(int, input().split())
	M = count = 0
	for i in range(1, P + 1):
		for j in range(1, P + 1):
			for k in range(1, P + 1):
				m = N % i % j % k % N
				if M < m:
					count = 1
					M = m
				elif M == m:
					count += 1
	print(count)


import math
t = int(input())
for x in range(t):
	(n, p) = list(map(int, input().split()))
	r = p
	if n == 1:
		print(p ** 3)
		continue
	elif n < p:
		p = n - 1
	v = math.ceil(n / p)
	v1 = n // p + 1
	myvar = max(v, v1)
	mytemp = math.ceil(n / myvar)
	mytemp1 = n // myvar + 1
	result = n % max(mytemp, mytemp1)
	if result > 0:
		b = (r - result) ** 2
		c = (r - n) * (r - result)
		d = (r - n) ** 2
		print(b + c + d)
	else:
		print(r ** 3)


t = int(input())
for i in range(t):
	(n, p) = map(int, input().split())
	max = n % (n // 2 + 1)
	if max == 0:
		print(p * p * p)
	else:
		print((p - max) * (p - max) + (p - max) * (p - n) + (p - n) * (p - n))


import math
for _ in range(int(input())):
	(n, p) = list(map(int, input().split()))
	ans = 0
	if n & 1 == 1:
		if n // 2 == 0:
			ans = p * p * p
			print(ans)
			continue
		ans += (p - n // 2) * (p - n // 2)
		ans += (p - n) * (p - n // 2)
	else:
		if n // 2 - 1 == 0:
			ans = p * p * p
			print(ans)
			continue
		ans += (p - n // 2 + 1) * (p - n // 2 + 1)
		ans += (p - n) * (p - n // 2 + 1)
	ans += (p - n) * (p - n)
	print(ans)


import math
import operator
for t in range(int(input())):
	(n, p) = list(map(int, input().split()))
	if n in range(1, 3):
		ans = p ** 3
	elif n == p:
		if n % 2 == 0:
			ans = (n / 2 + 1) ** 2
		else:
			ans = math.ceil(n / 2) ** 2
	elif p > n:
		gap = int(n / 2) * 3 + 6
		if n % 2 == 0:
			ini = (n / 2 + 1) ** 2
		else:
			ini = math.ceil(n / 2) ** 2
		ans = ini + (p - n) / 2 * (2 * gap + (p - n - 1) * 6)
	print(int(ans))


for _ in range(int(input())):
	(n, p) = map(int, input().split())
	i = n // 2 + 1
	j = n % i + 1
	k = n % i % j + 1
	m = n % i % j % k % n
	if n == 2 or n == 1:
		print(p * p * p)
	else:
		counti = 1
		countj = p - j + 1
		countk = p - k + 1
		count1 = counti * countj * countk
		count = count1
		if p > n:
			counti = p - n
			countj = 1
			countk = p - k + 1
			count2 = counti * countj * countk
			counti = p - n
			countj = p - n
			countk = 1
			count3 = counti * countj * countk
			if n % p % p % p % n == m:
				count3 += 1
			count += count2 + count3
		print(count)


import sys
f = sys.stdin
t = int(f.readline().rstrip())
for i in range(t):
	(n, p) = map(int, f.readline().rstrip().split())
	if n % 2 == 1:
		m = (n - 1) // 2
		if m == 0:
			x = p * p * p
		else:
			x = (p - m) * (p - m) + (p - n) * (p - m) + (p - n) * (p - n)
		print(x)
	else:
		m = n // 2 - 1
		if m == 0:
			x = p * p * p
		else:
			x = (p - m) * (p - m) + (p - n) * (p - m) + (p - n) * (p - n)
		print(x)


t = int(input())
for __ in range(t):
	(n, p) = [int(i) for i in input().split()]
	m = n % (n // 2 + 1)
	if m == 0:
		print(p ** 3)
	else:
		print((p - m) * (p - m) + (p - n) * (p - m) + (p - n) * (p - n))


a = int(input())
for i in range(a):
	(N, P) = map(int, input().split())
	if N == 1 or N == 2:
		ans = P ** 3
	else:
		r = N - (N // 2 + 1)
		ans = (P - r) ** 2 + (P - N) * (P - r) + (P - N) ** 2
	print(ans)


t = int(input())
for i in range(t):
	(n, p) = map(int, input().split())
	a = 0
	count = 0
	if n == 2 or n == 1:
		count = p * p * p
	elif p == n and (n != 1 or n != 2):
		count = count + (p - n % (n // 2 + 1)) * (p - n % (n // 2 + 1))
	else:
		b = p - n % (n // 2 + 1)
		c = p - n % (n // 2 + 1)
		count = b * c
		a = int(p - (n + 1)) + 1
		count = count + a * c
		b = p - (n + 1) + 1
		count += b * a
	print(count)


try:
	t = int(input())
	while t:
		(n, p) = [int(x) for x in input().split()]
		M = n - (int(n / 2) + 1)
		if M == 0:
			print(p * p * p)
		else:
			b = p - n
			ans = (p - M + b) * (p - M) + b * b
			print(ans)
		t = t - 1
except:
	pass


t = int(input())
for i in range(0, t):
	np = list(map(int, input().strip().split()))
	n = np[0]
	p = np[1]
	o = int(n / 2 + 1)
	mod = n % o
	if mod != 0:
		s = (p - n) * (p - n)
		s += (p - n) * (p - mod)
		s += (p - mod) * (p - mod)
		print(s)
	else:
		print(p * p * p)


t = int(input())
for _ in range(t):
	(n, p) = [int(i) for i in input().split()]
	k = n // 2 + 1
	if n == 1 or n == 2:
		print(p * p * p)
	else:
		k = n % k
		s = (p - k) ** 2
		d = (p - n) * (p - k)
		e = (p - n) * (p - n)
		print(d + e + s)


for _ in range(int(input())):
	(n, p) = list(map(int, input().split()))
	cnt = 0
	king = 0
	queen = 0
	if n % 2 == 0:
		m = n // 2 - 1
	else:
		m = (n - 1) // 2
	if m == 0:
		cnt += p * p * p
	else:
		king = p - m
		queen = p - n
		cnt = king * king + queen * (king + queen)
	print(cnt)


t = int(input())
for i in range(t):
	(n, p) = map(int, input().split())
	if n == p:
		if n == 1:
			print(1)
		elif n == 2:
			print(8)
		else:
			h = 3
			county = 2
			while h < n:
				h = h + 2
				county += 1
			o = county * county
			print(o)
	else:
		if n & 1:
			mex = n // 2
		else:
			mex = n // 2 - 1
		s = n - mex % n
		if n == 2:
			ans = p ** 3
			print(ans)
		elif n & 1 and n != 1:
			ans = (p - s + 1) * (p - s + 1) + (p - (n + 1) + 1) * (p - s + 1) + (p - (n + 1) + 1) ** 2
			print(ans)
		elif n & 1:
			print(p ** 3)
		else:
			ans = (p - s + 2) * (p - s + 2) + (p - (n + 1) + 1) * (p - s + 2) + (p - (n + 1) + 1) * (p - (n + 1) + 1)
			print(ans)


t = int(input())
while t > 0:
	t -= 1
	li = list(map(int, input().split()))
	n = li[0]
	p = li[1]
	if n % 2 is 0:
		quo_max = int(n / 2 + 1)
	else:
		quo_max = int((n + 1) / 2)
	rem_max = n % quo_max
	if n is 1 or n is 2:
		print(p * p * p)
	elif n == p:
		print((p - rem_max) * (p - rem_max))
	else:
		print((p - rem_max) * (p - rem_max) + (p - n) * (p - rem_max) + (p - n) * (p - n))


t = int(input())
for i in range(t):
	k = input().split()
	n = int(k[0])
	p = int(k[1])
	bade = 0
	ans = 0
	rem_bade = 0
	if n < p and n % 2 == 0:
		rem = int(n / 2 - 1)
		if rem != 0:
			bade = p - n
			rem_bade = p - rem
			ans = rem_bade * rem_bade + bade * rem_bade + bade * bade
		else:
			ans = p * p * p
		print(ans)
	elif n < p and n % 2 != 0:
		rem = int(n / 2)
		if rem != 0:
			bade = p - n
			rem_bade = p - rem
			ans = rem_bade * rem_bade + bade * rem_bade + bade * bade
		else:
			ans = p * p * p
		print(ans)
	elif n == p and n % 2 != 0:
		rem = int(n / 2)
		if rem != 0:
			ans = (p - rem) * (p - rem)
		else:
			ans = p * p * p
		print(ans)
	elif n == p and n % 2 == 0:
		rem = int(n / 2 - 1)
		if rem != 0:
			ans = (p - rem) * (p - rem)
		else:
			ans = p * p * p
		print(ans)


R = lambda : map(int, input().split())
t = int(input())
while t > 0:
	t = t - 1
	(n, p) = R()
	if n % 2 == 0:
		c = n // 2 + 1
	else:
		c = (n + 1) // 2
	m = n % c
	if n <= 2:
		print(p * p * p)
	else:
		k = p - m
		l = p - n
		print(k * k + l * k + l * l)


t = int(input())
for i in range(t):
	(n, p) = map(int, input().split(' '))
	if n == 1 or n == 2:
		print(p * p * p)
	else:
		if n % 2 == 0:
			m = n // 2 - 1
			z = (p - m) * (p - m) + (p - n) * (p - m) + (p - n) * (p - n)
		else:
			m = n // 2
			z = (p - m) * (p - m) + (p - n) * (p - m) + (p - n) * (p - n)
		print(z)


import math
T = int(input())
for i in range(T):
	input_line = input().split()
	N = int(input_line[0])
	P = int(input_line[1])
	ans = 0
	if N <= 2:
		print(P ** 3)
	else:
		part_1 = (P - math.ceil(N / 2) + 1) ** 2
		part_2 = (P - N) * (P - math.ceil(N / 2) + 1)
		part_3 = (P - N) ** 2
		ans = part_1 + part_2 + part_3
		print(ans)


t = int(input())
for i in range(t):
	(n, p) = input().split()
	n = int(n)
	p = int(p)
	if n == 1 or n == 2:
		print(p ** 3)
	else:
		a = n // 2 + 1 + p - n
		b = p - n
		case1 = a ** 2
		case2 = a * b
		case3 = b ** 2
		print(case1 + case2 + case3)


t = int(input())
ans = list()
while t != 0:
	(n, p) = [int(x) for x in input().split()]
	r = p - n
	a = int(n / 2) + 1
	temp = 0
	if n == 1 or n == 2:
		temp = p * p * p
	elif n == p:
		temp = a * a
	else:
		temp = 3 * r * r + 3 * a * r + a * a
	ans.append(temp)
	t = t - 1
for x in ans:
	print()
	print(x)


t = int(input())
while t:
	l1 = list(map(int, input().split(' ')))
	n = l1[0]
	p = l1[1]
	if n == 1 or n == 2:
		print(p ** 3)
	elif n % 2 == 1:
		v = 3 * (p - 1) * (p - n) + (int(n / 2) + 1) ** 2 - int(int(n / 2) - 1) * (3 * (p - n))
		print(v)
	else:
		v1 = 3 * (p - 1) * (p - n) + (int(n / 2) + 1) ** 2 - int(n / 2) * (3 * (p - n)) + 6 * (p - n)
		print(v1)
	t = t - 1


T = int(input())
for i in range(T):
	(n, p) = map(int, input().split())
	if n > 2:
		if n % 2 == 0:
			x = (n + 2) // 2
		elif n % 2 == 1:
			x = (n + 1) // 2
		y = n % x + 1
		q = (p - y + 1) ** 2
		r = (p - y + 1) * (p - n) + (p - n) ** 2
		print(q + r)
	else:
		print(p ** 3)