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

Абелеві групи

Абелеві групи

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

У країні Берляндії у місті N є така традиція. Якщо дівчина бажає вийти заміж за молодого человіка, а у нього у планах відсутнє бажання дарувати їй усі можливі намиста з шести бусинок, то вона повинна кожен день дарувати йому одну нову абелеву групу порядка N. І лише коли усі можливі абелеві групи подаровано, молодой человік погодиться кожен день дарувати їй одне нове намисто з шести бусинок, і в решті решт вони одружаться. При цьому якщо дві абелеві групи ізоморфні, то вони вважаються однаковими і дарувати потрібно лише одну з них. Дівчинка на ім'я Афіна закохалась у одного дуже занятого програміста на ім'я Петя. Тепер вона хоче взнати скільки днів їй потрібно дарувати йому абелеві групи, до того як він погодиться дарувати їй намиста.

Нагадаємо сновні поняття і факти відносно абелевих груп.

Абелева група це пара G=(A,*), де A - це деяка множина, а * - це бінарна операція на A, тобто довільним двом елементам a та b з A ставиться у відповідність елемент a*b, який також належить A. При цьому повинні бути виконані наступні властивості, які називають аксіомами абелевої групи:

(i) Асоціативність: для довільних a, b, cA виконується рівність (a*b)*c=a*(b*c).

(ii) Існує eA таке, що для довільного aA виконуються рівності a*e=e*a=a.

(iii) Для довільного aA існує bA таке, що виконуються рівності a*b=b*a=e.

(iv) Комутативність: для довільних a, bA виконується рівність a*b=b*a.

Важливим прикладом абелевої групи є циклічна група порядку n: множина чисел від 0 до n-1 з операцією додавання по модулю n. Вона позначається як Z_n.

Прямою сумою двох абелевих груп G=(A,*) і H=(B,·) називається пара GH =(C,×), C={(a,b) : aA, bB} і (a_1, b_1)×(a_2, b_2) = (a_1 * a_2, b_1 · b_2) для усіх a_1, a_2A і b_1, b_2B.

Дві групи G=(A,*) і H=(B,·) називаються ізоморфними, якщо існує взаємно однозначне відображення f з A на B таке, що f(a_1)·f(a_2)=f(a_1*a_2) для усіх a_1, a_2A.

Фундаментальна теорема теорії абелевих груп стверджує, що довільна скінчена абелева група ізоморфна прямій сумі деяких циклічних груп.

Китайська теорема про залишки стверджує, що Z_mn ізоморфно Z_mZ_n тоді і лише тоді, коли m і n взаємно прості.

Останні два твердження дозволяють описувати усі абелеві групи порядку n з точністю до ізоморфізму.

Наприклад, якщо n - просте, то усі групи порядку n ізоморфні Z_n.

Інує 2 неізоморфні групи порядку 4: Z_4 і Z_2Z_2.

Існує 3 неізоморфні групи порядку 27: Z_27, Z_9Z_3 у Z_3Z_3Z_3.

Існує 4 неізоморфні групи порядку 36: Z_4Z_9, Z_2Z_2Z_9, Z_4Z_3Z_3 і Z_2Z_2Z_3Z_3.

Вхідні дані

У першому рядку вхідного файлу задано натуральне число T500, кількість тестів. У кожному з наступнх T рядків задано натуральне число N10^18.

Вихідні дані

Для кожного числа N з вхідного файлу виведіть у окремому рядку кількість абелевих груп порядку N з точністю до ізоморфізму.

Приклад

Вхідні дані #1
4
3
4
27
36
Вихідні дані #1
1
2
3
4