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

Диофант Александрийский

Диофант Александрийский

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

Диофант Александрийский - был такой математик в Египте, живший в Александрии. Он был одним из первых математиков, исследовавших уравнения, где переменные были ограничены целыми значениями. Именно в его честь эти уравнения обычно называют диофантовыми уравнениями. Одно из самых известных диофантовых уравнений есть уравнение это x^n + y^n = z^n. Ферма предположил, что при n > 2 нет доказательства существования решений в общем виде с целыми положительными значениями х, у и z. Доказательство этой теоремы (называемой великой теоремой Ферма) было найден только недавно Эндрю Вайлсом, английским математиком, работающим в Принстонском университете (США).

Рассмотрим следующее диофантово уравнение:

1/x + 1/y = 1/n где x, y, nN^{+} (1)

Диофанта заинтересовал следующий вопрос: при заданном n сколько различных решений (т.е. решений, удовлетворяющих условию ху) имеет уравнение (1)? Например, при n = 4 есть ровно три различных решения:

1 / 5 + 1 / 20 = 1 / 4 1 / 6 + 1 / 12 = 1 / 4 1 / 8 + 1 / 8 = 1 / 4

Очевидно, что перечисление этих решений может стать утомительным для больших значений n. Можете ли вы помочь Диофанту быстро вычислить количество различных решений этого уравнения для больших значений n?

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

Первая строка содержит количество тестовых случаев. Каждый тестовый случай расположен в отдельной строке, содержащей одно число n (1n10^9).

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

Выходные данные для каждого тестового случая начинается со строки, содержащей сообщение " Scenario #i:", где i - это номер тестового случая, начиная с 1. Далее в следующей строке выводится количество различных решений уравнения (1) для заданного значения n. Завершайте вывод ответа для каждого тестового случая пустой строкой.

Пример

Входные данные #1
2
4
1260
Выходные данные #1
Scenario #1:
3

Scenario #2:
113