eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Прямые

Прямые

Лимит времени 10 секунд
Лимит использования памяти 64 MiB

Рассмотрим положительное целое N. Пусть A, B и C – такие неотрицательные целые числа, что A + B + C = N. Пусть на координатной оси отмечено N точек с одинаковым интервалом между каждыми двумя соседними. Проведите прямые под углом 45 градусов к координатной оси через A левых точек, проведите прямые под углом 90 градусов к координатной оси через B следующих точек и под углом 135 градусов к координатной оси – через оставшиеся C точек. Эти прямые пересекутся в некотором количестве точек.

prb99

Для ясности смотрите рисунок, где указан случай 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.

Пример

Входные данные #1
3
2
3
5
Выходные данные #1
Case #1: 3
Case #2: 13
Case #3: 91