题目描述

冬天来了，你需要给你的房子装上暖气

你的房子有$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$

样例

4
1 10000
10000 1
2 6
4 6

100000000
1
18
10