import math

def sum_square_divisor(x):
    sum_num=0
    for i in range(1,int(math.sqrt(x))+1):
        if(x%i==0):
            if(x/i==i):
                sum_num+=i*i
            else:
                sum_num+=i*i
                sum_num+=int((x/i))*int((x/i))
    return sum_num

def isaperfectsquare(x):
    sr=math.sqrt(x)
    return ((sr-math.floor(sr))==0)

q = int(input())
for i in range(q):
    arr=list(map(int, input().split()))
    N=arr[0]
    K=arr[1]
    check_list=[]
    finalsum=0
    for n in range(1,N+1):
        if(n==1):
            for j in range(K+1):
                check_pos=n+j
                check_neg=n-j
                if(check_neg>0):
                    if(isaperfectsquare(check_pos) or isaperfectsquare(check_neg)):
                        finalsum+=n
                        break
                else:
                    if(isaperfectsquare(check_pos)):
                        finalsum+=n
                        break
            
        else:
            divisor_sum=sum_square_divisor(n)
            for j in range(K+1):
                check_pos=divisor_sum+j
                check_neg=divisor_sum-j
                if(check_neg>0):
                    if(isaperfectsquare(check_pos) or isaperfectsquare(check_neg)):
                        finalsum+=n
                        break
                else:
                    if(isaperfectsquare(check_pos)):
                        finalsum+=n
                        break
   
    print(finalsum)

import math

def div(n):
    return set(x for tup in ([i, n//i] 
                for i in range(1, int(n**0.5)+1) if n % i == 0) for x in tup)
def sq(l):
    return [i ** 2 for i in l]
    
def output(n,k):
    o=[]
    for i in range(2,n+1,1):
        n_div=div(i)
        sq_div=sq(n_div)
        snds=sum(sq_div)
        rtsq=math.sqrt(snds)
        x=math.ceil(rtsq)
        y=math.floor(rtsq)
        if(abs((x*x)-snds)<=k or abs((y*y)-snds)<=k):
            o.append(i)
    os=sum(o)
    return os+1

n=int(input())
cont = []
for j in range(n):
    cont.append(list(map(int, input().rstrip().split())))
for i in range(n):
    print(output(cont[i][0],cont[i][1]))