几天前,您买了一套新房子,现在正计划开始装修。由于您所在地区的冬天可能非常寒冷,您需要决定如何为家里的房间供暖。
你的房子有 $$$n$$$ 个房间。在第 $$$i$$$ 个房间中,您最多可以安装 $$$c_i$$$ 暖气片。每个散热器可以有多个部分,但具有 $$$k$$$ 部分的散热器的成本等于 $$$k^2$$$ burles。
由于房间可以有不同的大小,您计算出第 $$$i$$$ 个房间总共至少需要 $$$sum_i$$$ 个部分。
对于每个房间,计算安装最多 $$$c_i$$$ 个散热器的最低成本,且总节数不少于 $$$sum_i$$$。
输入
第一行包含单个整数 $$$n$$$ ($$$1 \le n \le 1000$$$) — 房间数量。
接下来的 $$$n$$$ 行中的每一行都包含某个房间的描述。第 $$$i$$$ 行包含两个整数 $$$c_i$$$ 和 $$$sum_i$$$ ($$$1 \le c_i, sum_i \le 10^4$$$) — 分别是第 $$$i$$$ 房间中散热器的最大数量和分区的最小总数。
输出
对于每个房间,打印一个整数 — 安装最多 $$$c_i$$$ 散热器且总节数不少于 $$$sum_i$$$ 的最低可能成本。
示例
输入 #1
4 1 10000 10000 1 2 6 4 6
输出 #1
100000000 1 18 10
注意
在第一个房间中,您只能安装一个散热器,因此最好使用具有 $$$sum_1$$$ 部分的散热器。散热器的成本等于$$$(10^4)^2 = 10^8$$$。
在第二个房间,您最多可以安装 $$$10^4$$$ 散热器,但由于总共只需要一节,因此最好购买一台散热器。
在第三个房间,有 $$$7$$$ 种安装散热器:$$$[6, 0]$$$, $$$[5, 1]$$$, $$$[4, 2]$$$, $$$[3, 3]$$$, $$$[2, 4]$$$, $$$[1, 5]$$$, $$$[0, 6]$$$。最佳变体是 $$$[3, 3]$$$,成本为 $$$3^2+ 3^2 = 18$$$。