Главный начальник всех водителей маршрутных такси Ровшан Мухамедович Шумахер уже редко водит свой автомобиль марки «Газель». Всё чаще он сидит дома за бутылочкой кофе и размышляет о том, как бы повысить прибыль с маршрутных такси. Не так давно он придумал систему тарификации, при которой проезд будет дорожать в зависимости от числа остановок, которое хочет проехать пассажир. Теперь он задумался, как бы лучше установить зависимость оплаты за проезд от числа остановок.

Сначала он хотел просто добавлять какую-нибудь фиксированную сумму в один условный рубль к проезду за каждую остановку, но ему показалось это не очень выгодно, да и к тому же слишком банально. Ровшан Шумахер любил быструю езду, русский шансон и деньги, но не любил ничего банального. Тогда, вспомнив школьный курс арифметики, он решил сделать проезд дорожающим, как квадраты натуральных чисел. Получилось неплохо, да и гораздо прибыльнее, чем раньше. В конце концов, он задумался, как разделять тарификацию на разные маршруты, ведь он хотел часть маршрутов сделать в принципе дороже, чем часть других. Умножать на какой-нибудь коэффициент показалось ему слишком банально.

Тогда он подумал, что кроме квадратных чисел должны существовать ещё треугольные, пятиугольные и тому подобные. При этом он рассуждал так. Если квадрат числа $$$n$$$ — это число одинаковых окружностей, из которых, сложив их вплотную, можно составить квадрат со стороной в $$$n$$$ таких окружностей (квадрат образуют центры крайних окружностей, соединённые отрезками), то, например, треугольник числа $$$n$$$ — это число окружностей, из которых можно составить правильный треугольник со стороной в $$$n$$$ таких окружностей. Так же легко это понятие обобщается и на фигуры с большим количеством углов.

Идея Ровшану очень понравилась. Он сразу распределил маршруты по ценности. Маршрут имеет ценность $$$k$$$, если плата за проезд по нему возрастает как $$$k$$$-угольник числа остановок, которые хочет проехать пассажир.

Поскольку водители не смогут быстро посчитать, сколько брать за проезд, зная только эту идею, нужно было быстро составить список тарифов на каждый маршрут. Ваша задача — написать для этого программу, которая будет интегрироваться в бортовой компьютер каждого автомобиля марки «Газель».