Все красное отпугивает монстра Ниана. Например, красная бумага и... вы, красные на Codeforces в будущем или уже сейчас.
Большой Банбан приобрел кусочек бумаги с бесконечной целочисленной решеткой, точки решетки образуют квадраты равной площади. Его любимая замкнутая линия — окружность, т. к. окружность одновременно проста и красива. Он приготовился вырезать что-нибудь красивое, предварительно нарисовав несколько цветных окружностей.
Он нарисовал n концентрических окружностей и пронумеровал их от 1 до n таким образом, что центры всех окружностей совпадают с одной и той же точкой целочисленной решетки, а радиус k-й окружности равен 
длинам кратчайшего периода решетки.
Определим красоту точки целочисленной решетки как сумму номеров окружностей, внутри или на границе которых лежит эта точка. Банбан хотел попросить вас определить суммарную красоту всех точек целочисленной решетки, но передумал.
Определим суммарную красоту всех точек целочисленной решетки на ткани с n окружностями ка f(n). Вычислите 
.
Примечание
Решетка с 5 окружностями изображена на рисунке ниже.
Всего есть 5 типов точек целочисленной решетки, красота каждой красной точки равна 1 + 2 + 3 + 4 + 5 = 15, красота каждой оранжевой точки равна 2 + 3 + 4 + 5 = 14, красота каждой зеленой точки равна 4 + 5 = 9, красота каждой синей точки равна 5, а красота каждой серой точки равна 0. Итого, f(5) = 5·15 + 4·14 + 4·9 + 8·5 = 207.
Аналогично, f(1) = 5, f(2) = 23, f(3) = 50, f(4) = 102, и поэтому 
.