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

Starter code:

Solutions:
for __ in range(int(input())):
 n,p=list(map(int,input().split()))
 d=n%(n//2+1)
 if(d==0):
  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)

# cook your dish here
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)
 else:
  if 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
   
   
    
   


# cook your dish here
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

 # cook your dish here
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)
  else:
   if(n%2==0):
    print((p-int(n/2)+1)**2+(p-n)*(p-int(n/2)+1)+(p-n)**2)
   else:
    print((p-int(n/2))**2+(p-n)*(p-int(n/2))+(p-n)**2)
except Exception:
 pass
   


 # cook your dish here
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)
  else:
   if(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
   


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)
 else:
  if(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)

t = int(input())
for test in range(t):
 n,p = map(int, input().split())
 m = round(n/2 - 0.7) #max possible score when i,j,k are the next integer         greater than n/2
 if m==0:
  choices = p**3
 else:
  choices = (p-m)**2 + (p-n)**2 + (p-m)*(p-n)
 print(choices)

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

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
  


# -*- coding: utf-8 -*-
"""
@author: anishukla
"""
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)

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


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


R = lambda : list(map(int,input().split()))
t = int(input())
for _ in range(t):
 n,p = R()
 max_no =n-(int(n/2)+1)
 # print(max_no)
 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)


for _ in range(int(input())):
 n,p=map(int,input().split())
 d=n%(n//2+1)
 #print("d = ",d)
 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 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)

def main():
 for i in range(int(input())):
  n, p = list(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()




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)

# cook your dish here
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))
 #print(ar)
 for i in ar:#range(P):
  for j in ar:#range(P):
   for k in ar:#range(P):
    M = (((N%i)%j)%k)%N
    if M > MaxM:
     count = 1
     MaxM = M
     #print("{} {} {} {}".format(i,j,k,MaxM))
    elif M == MaxM:
     count = count + 1
     #print("{} {} {} {}".format(i,j,k,MaxM))
 print(count)
 


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


# cook your dish here
ts=int(input())
while ts>0:
 num,p=list(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)
 ts=ts-1