Диофант Александрийский
Діофант Александрійський - був такий математик у Єгипті, який жив в Александрії. Він був одним з перших математиків, які досліджували рівняння, де змінні було обмежено цілими значеннями. Саме у його честь ці рівняння звичайно називають діофантовими рівняннями. Одним з самих відомих діофантових рівнянь є рівняння x^n + y^n = z^n. Ферма припустив, що при n > 2 не існує доведення існування розв'язків у загальному випадку з цілими додатними значеннями х, у та z. Доведення цієї теореми (яку називають великою теоремою Ферма) було знайдено лише недавно Ендрю Вайлсом, англійським математиком, який працює у Прінстонському університеті (США).
Розглянемо наступні діофантове рівняння:
1/x + 1/y = 1/n где x, y, n ∈ N^{+} (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 (1 ≤ n ≤ 10^9).
Вихідні дані
Вихідні дані для кожного тестового випадку починається з рядка, який містить повідомлення " Scenario #i:", де i - це номер тестового випадку, починаючи з 1. Далі у наступному рядку виводиться кількість різних розв'язків рівняння (1) для заданого значення n. Завершуйте виведення відповіді для кожного тестового випадку порожнім рядком.