CF1260A.Heating

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$.

几天前，你购买了一栋新房子，现在正计划开始装修。由于你所在地区的冬季可能非常寒冷，你需要决定如何为房子里的各个房间供暖。

你的房子共有 $n$ 个房间。在第 $i$ 个房间中，最多可安装 $c_i$ 个暖气片。每个暖气片可以拥有多个散热片（sections），但一个含有 $k$ 个散热片的暖气片的成本为 $k^2$ 卢布（burles）。

由于各房间面积不同，你已计算出：第 $i$ 个房间所需的散热片总数至少为 $sum_i$。

对每个房间，请计算在最多安装 $c_i$ 个暖气片、且散热片总数不少于 $sum_i$ 的前提下，所能达到的最小总成本。

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.

第一行包含一个整数 $n$（$1 \le n \le 1000$）—— 房间的数量。

接下来的 $n$ 行，每行描述一个房间。第 $i$ 行包含两个整数 $c_i$ 和 $sum_i$（$1 \le c_i, sum_i \le 10^4$）—— 分别表示第 $i$ 个房间中散热器的最大数量以及该房间所需散热片的最小总数。

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$.

对每个房间，输出一个整数——安装至多 $c_i$ 个暖气片、且总散热片数不少于 $sum_i$ 的最小可能花费。

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$.

在第一个房间中，你只能安装一个散热器，因此最优方案是使用具有 $sum_1$ 个散热片的散热器。该散热器的成本为 $(10^4)^2 = 10^8$。

在第二个房间中，你最多可安装 $10^4$ 个散热器，但由于总共仅需 1 个散热片，因此最优方案是购买一个含 1 个散热片的散热器。

在第三个房间中，共有 $7$ 种散热器安装方案：$[6, 0]$、$[5, 1]$、$[4, 2]$、$[3, 3]$、$[2, 4]$、$[1, 5]$、$[0, 6]$。其中最优方案为 $[3, 3]$，其成本为 $3^2 + 3^2 = 18$。