Діофант Олександрійський#2528

Діофант Олександрійський

1 секунда

128 мегабайтів

Дуже легка

Діофант Олександрійський був єгипетським математиком, який жив в Александрії. Він став одним із перших математиків, які вивчали рівняння, де змінні обмежуються цілими значеннями. На його честь ці рівняння називають діофантовими рівняннями. Одне з найвідоміших діофантових рівнянь має вигляд $x^{n} + y^{n} = z^{n}$ x^n + y^n = z^n. Ферма припустив, що для $n > 2$ n > 2 це рівняння не має розв'язків у додатних цілих числах $x$ , $y$ і $z$ . Доведення цієї теореми, відомої як Велика теорема Ферма, було знайдено лише нещодавно Ендрю Вайлсом, англійським математиком із Принстонського університету (США).

Розглянемо наступне діофантове рівняння:

\frac{1}{x} + \frac{1}{y} = \frac{1}{n}

\frac{1}{x} + \frac{1}{y} = \frac{1}{n}

де $x, y, n \in N^{+} (1)$ x, y, n \in \mathbb{N}^+ \qquad (1)

Діофанта цікавило наступне питання: для заданого $n$ , скільки різних розв'язків (тобто таких, що задовольняють $x \leq y$ x \leq y) має рівняння $(1)$ ? Наприклад, для $n = 4$ n = 4 існує рівно три різних розв'язки:

\frac{1}{5} + \frac{1}{20} = \frac{1}{4} \frac{1}{6} + \frac{1}{12} = \frac{1}{4} \frac{1}{8} + \frac{1}{8} = \frac{1}{4}

\frac{1}{5} + \frac{1}{20} = \frac{1}{4} \\ \frac{1}{6} + \frac{1}{12} = \frac{1}{4} \\ \frac{1}{8} + \frac{1}{8} = \frac{1}{4}

Очевидно, перебір цих розв'язків може бути трудомістким для великих $n$ . Чи зможете ви допомогти Діофанту швидко підрахувати кількість різних розв'язків для великого $n$ ?

Вхідні дані

Перший рядок містить кількість тестових випадків. Кожен тестовий випадок заданий у окремому рядку та містить одне ціле число $n$ ( $1 \leq n \leq 1 0^{9}$ 1 \leq n \leq 10^9).

Вихідні дані

Вивід для кожного тесту починається з рядка Scenario #i:, де $i$ — номер тесту, починаючи з $1$ . У наступному рядку слід вивести кількість різних розв'язків рівняння $(1)$ для заданого значення $n$ . Після кожного тесту виведіть порожній рядок.

Приклади

Приклад 1