A. Отопление
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Несколько дней назад вы приобрели новый дом и сейчас планируете провести в нем капитальный ремонт. Так как зимы в вашем регионе могут быть очень суровыми, вам нужно определиться с системой отопления в каждой комнате.

У вас в доме $$$n$$$ комнат. В $$$i$$$-й комнате вы можете установить не более $$$c_i$$$ радиаторов системы отопления. Каждый радиатор может иметь несколько секций, но стоимость радиатора из $$$k$$$ секций равна $$$k^2$$$ бурлей.

Так как комнаты имеют разные размеры, то вы рассчитали, что на обогрев $$$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$$$.

Пример
Входные данные
4
1 10000
10000 1
2 6
4 6
Выходные данные
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$$$.