Прямые
Рассмотрим положительное целое N. Пусть A, B и C – такие неотрицательные целые числа, что A + B + C = N. Пусть на координатной оси отмечено N точек с одинаковым интервалом между каждыми двумя соседними. Проведите прямые под углом 45 градусов к координатной оси через A левых точек, проведите прямые под углом 90 градусов к координатной оси через B следующих точек и под углом 135 градусов к координатной оси – через оставшиеся C точек. Эти прямые пересекутся в некотором количестве точек.
Для ясности смотрите рисунок, где указан случай N = 5, A = 1, B = 2, C = 2. Всего получилось 6 точек пересечения.
Ваша задача довольно проста – для заданного N посчитать сумму количеств точек пересечения для всех возможных троек A, B, C.
Входные данные
Первая строка ввода содержит количество тестов T (1 ≤ T ≤ 1000).
Каждая из следующих T строк содержит число N (2 ≤ N ≤ 10^6) – количество точек на прямой в данном тесте.
Выходные данные
Выведите T строк вида Case #A: B, где A – номер теста (начиная с 1), B – сумма количеств точек пересечения для заданного N.