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

Подсчет курей

Подсчет курей

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

Куриный фермер Хиоян приобрел трех новых курей Люси, Чарли и ЦЦ. Хиоян хочет построить изгородь таким образом, чтобы каждая из них имела свой собственный беспрепятственный вид на округу. Изгородь должна иметь три стороны; это даст возможность каждой курице прогуливаться взад-вперед вдоль собственной стороны, не мешая другим. Хиоян нашел рулон проволочной сетки (ограждения) в сарае длиной в точности p футов. Она хочет вычислить количество способов, которыми сможет построить изгородь для курей таким образом, чтобы каждая ее сторона была целочисленной и при этом был бы использован весь рулон. Изгороди, полученные вращениями, считаются одинаковыми. Однако изгороди, полученные отражениями, могут быть разными (см. внизу).

prb5125.gif

Входные данные

Первая строка содержит количество тестов t (1t1000). Каждый тест следует обрабатывать независимо от других.

Каждый тест состоит из одной строки, содержащей номер теста и длину рулона сетки n (3n10000).

Выходные данные

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

Пример

Входные данные #1
5
1 3
2 11
3 12
4 100
5 9999
Выходные данные #1
1 1
2 5
3 4
4 392
5 4165834
Источник 2012 ACM Greater New York Region, October 28