Several days ago you bought a new house and now you are planning to start a renovation. Since winters in your region can be very cold you need to decide how to heat rooms in your house.

Your house has $n$ rooms. In the $i$-th room you can install at most $c_i$ heating radiators. Each radiator can have several sections, but the cost of the radiator with $k$ sections is equal to $k^2$ burles.

Since rooms can have different sizes, you calculated that you need at least $sum_i$ sections in total in the $i$-th room. 

For each room calculate the minimum cost to install at most $c_i$ radiators with total number of sections not less than $sum_i$.


-----Input-----

The first line contains single integer $n$ ($1 \le n \le 1000$) — the number of rooms.

Each of the next $n$ lines contains the description of some room. The $i$-th line contains two integers $c_i$ and $sum_i$ ($1 \le c_i, sum_i \le 10^4$) — the maximum number of radiators and the minimum total number of sections in the $i$-th room, respectively.


-----Output-----

For each room print one integer — the minimum possible cost to install at most $c_i$ radiators with total number of sections not less than $sum_i$.


-----Example-----
Input
4
1 10000
10000 1
2 6
4 6

Output
100000000
1
18
10



-----Note-----

In the first room, you can install only one radiator, so it's optimal to use the radiator with $sum_1$ sections. The cost of the radiator is equal to $(10^4)^2 = 10^8$.

In the second room, you can install up to $10^4$ radiators, but since you need only one section in total, it's optimal to buy one radiator with one section.

In the third room, there $7$ variants to install radiators: $[6, 0]$, $[5, 1]$, $[4, 2]$, $[3, 3]$, $[2, 4]$, $[1, 5]$, $[0, 6]$. The optimal variant is $[3, 3]$ and it costs $3^2+ 3^2 = 18$.

Difficulty: interview

Starter code:

Solutions:
"""This code was written by
Russell Emerine - linguist,
mathematician, coder,
musician, and metalhead."""

n = int(input())
for _ in range(n):
  c, s = list(map(int, input().split()))
  a = s // c
  r = s % c
  print((c - r) * a ** 2 + r * (a + 1) ** 2)



t=int(input())
for nt in range(t):
    c,s=[int(k) for k in input().strip().split(" ")]
    res=0
    nba= s//c
    nbap=nba+1
    np= s%c
    na= c-np
    print(np*nbap*nbap + na *nba*nba)



n = int(input())

for _ in range(n):
    c, s = list(map(int, input().split()))
    a = s // c
    b = s % c
    print(b * (a + 1) ** 2 + (c - b) * a ** 2)


n = int(input())

for i in range(n):
    a,b = map(int,input().split())
    c,d = divmod(b,a)
    res = 0
    for j in range(d):
        res += (c + 1) ** 2
    for j in range(a - d):
        res += c ** 2
    print(res)

n = int(input())
for i in range(n):
    c, s = tuple(map(int, input().split()))

    standart = s // c
    ost = s % c

    print((standart + 1) ** 2 * ost + standart ** 2 * (c - ost))


n = int(input())
for i in range(n):
    c, s = list(map(int, input().strip().split()))
    left = s % c
    v = s // c
    o = 0
    for i in range(left):
        o += (v + 1) ** 2
    for i in range(left, c):
        o += v ** 2
    print(o)


n = int(input())
for i in range(n):
    c,s = map(int, input().split())
    r = s//c
    # s%c部屋r+1
    l = s%c
    ans = r*r*(c-l) + (r+1)**2*l
    print(ans)

n=int(input())
for i in range(n):
    a,b=list(map(int,input().split()))
    if b<a:
        print(b)
        continue
    else:
        ss=b//a
        tt=b%a
        tot=0
        tot+=a*(ss**2)
        tot+=tt*(ss+ss+1)
        print(tot)
        


t=int(input())
for _ in range(t):
    a,b=map(int,input().split())
    rem=b%a
    div=b//a
    print(b%a*(1+div)**2+(a-b%a)*(div)**2)

n = int(input())
for i in range(n):
    c, sum = map(int, input().split())
    k = sum // c
    cnt1 = sum % c
    cnt2 = c - cnt1
    print(cnt1 * (k + 1) ** 2 + cnt2 * k ** 2)

n = int(input())
for i in range(n):
    count, minSum = list(map(int, input().split()))
    ost = minSum % count
    r = minSum // count
    ans = (r**2) * count
    ans -= ost * (r**2)
    ans += ((r+1) ** 2) * ost
    print(ans)


import sys
input = sys.stdin.readline

N = int(input())
AB = [list(map(int, input().split())) for _ in range(N)]

for a , b in AB:
    c = b//a
    p1 = b%a
    ans = (c+1)**2*p1 + c**2*(a-p1)
    print(ans)

from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

t=I()
for _ in range(t):
    c,s=LI()
    a=s//c
    m=s-c*(s//c)
    an=(a**2)*(c-m)+m*(a+1)**2
    
    #show(an)
    print(an)
    

n = int(input())

for i in range(n):
    ans = 0
    num, m = list(map(int,input().split()))
    tmp = m // num
    add = m % num
    tmp2 = num - add
    ans = tmp ** 2 * tmp2 + (tmp + 1) ** 2 * add
    print(ans)
    
    
    


n = int(input())
for kase in range(n):
    c, sum = [int(x) for x in input().split()]
    x = sum // c
    y = sum % c
    ans = (x+1)*(x+1)*y + (x*x)*(c-y)
    print(ans)

n=int(input())
for ccc in range(n):
    c,s=list(map(int,input().split()))
    x=s//c
    y=s-x*c
    print(y*(x+1)**2+(c-y)*x**2)


n = int(input())
for i in range(n):
    (c, b) = list(map(int, input().split()))
    a = b // c
    b -= a*c
    ans = 0
    for j in range(c):
        if b == 0:
           ans += a*a
        else:
            ans += (a+1)*(a+1)
            b -= 1
    print(ans)

n = int(input())
for _ in range(n):
    
    c,sn = map(int,input().split())
    
    m = sn//c
    b = sn%c 
    
    ans = (m+1)*(m+1)*b + (m)*(m)*(c-b)
    
    print(ans)

def main():
    def solve():

        c, sum = map(int, input().split())
        pan = sum//c
        extra = sum % c
        result = (c - extra)*pan*pan + extra*(pan+1)*(pan+1)
        print(result)

    q = int(input())
    for _ in range(q):
        solve()


def __starting_point():
    main()
__starting_point()

n = int(input())
for i in range(n):
    a, b = map(int,input().split())
    ans = (b // a + 1) ** 2 * (b%a) + (b//a) ** 2 * (a-b%a)
    print(ans)

n=int(input())
for i in range(n):
    a,b=[int(x) for x in input().split(' ')]
    if a >= b:
        print(b)
    else:
        c=int(b/a)
        d=b%a
        print((a-d)*c**2+d*(c+1)**2)


for _ in range(int(input())):
    c, sm = list(map(int, input().split()))
    ans = ((sm // c + 1)**2) * (sm % c) + ((sm // c)**2) * (c - sm % c)
    print(ans)



from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()

for i in range(N):
    c,S = inpl()
    t1 = S//c
    t2 = t1 + 1
    ans = t1**2 * (c-(S%c)) + t2**2 * ((S%c))
    print(ans)