Heating

题意翻译

## 题目描述 冬天来了，你需要给你的房子装上暖气 你的房子有$n$个房间，每一个房间$i$最多可以装$c_i$个暖气，温暖度至少为$sum_i$，一个房间的温暖度为房间里所有暖气温暖度之和 对于一个温暖度为$k$的暖气，需要花费 $k^2$ 元，求对于每个房间，最少需要多少钱可以让子房间满足要求 ## 输入格式 第一行一个整数$n$，表示房间的总数 接下来$n$行，每行两个整数 第$i$行的两个整数分别表示$c_i,sum_i$ ## 输出格式 $n$行，每行一个整数表示第$i$个房间所需的最少花费 ### 数据范围 $1\le n \le 1000$ $1 \le c_i,sum_i \le 10^4$

题目描述

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

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

4
1 10000
10000 1
2 6
4 6

输出样例 #1

100000000
1
18
10

说明

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