Абелеві групи
У країні Берляндії у місті N є така традиція. Якщо дівчина бажає вийти заміж за молодого человіка, а у нього у планах відсутнє бажання дарувати їй усі можливі намиста з шести бусинок, то вона повинна кожен день дарувати йому одну нову абелеву групу порядка N. І лише коли усі можливі абелеві групи подаровано, молодой человік погодиться кожен день дарувати їй одне нове намисто з шести бусинок, і в решті решт вони одружаться. При цьому якщо дві абелеві групи ізоморфні, то вони вважаються однаковими і дарувати потрібно лише одну з них. Дівчинка на ім'я Афіна закохалась у одного дуже занятого програміста на ім'я Петя. Тепер вона хоче взнати скільки днів їй потрібно дарувати йому абелеві групи, до того як він погодиться дарувати їй намиста.
Нагадаємо сновні поняття і факти відносно абелевих груп.
Абелева група це пара G=(A,*), де A - це деяка множина, а * - це бінарна операція на A, тобто довільним двом елементам a та b з A ставиться у відповідність елемент a*b, який також належить A. При цьому повинні бути виконані наступні властивості, які називають аксіомами абелевої групи:
(i) Асоціативність: для довільних a, b, c A виконується рівність (a*b)*c=a*(b*c).
(ii) Існує e A таке, що для довільного a A виконуються рівності a*e=e*a=a.
(iii) Для довільного a A існує b A таке, що виконуються рівності a*b=b*a=e.
(iv) Комутативність: для довільних a, b A виконується рівність 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_2 A і b_1, b_2 B.
Дві групи G=(A,*) і H=(B,·) називаються ізоморфними, якщо існує взаємно однозначне відображення f з A на B таке, що f(a_1)·f(a_2)=f(a_1*a_2) для усіх a_1, a_2 A.
Фундаментальна теорема теорії абелевих груп стверджує, що довільна скінчена абелева група ізоморфна прямій сумі деяких циклічних груп.
Китайська теорема про залишки стверджує, що 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.
Вхідні дані
У першому рядку вхідного файлу задано натуральне число T ≤ 500, кількість тестів. У кожному з наступнх T рядків задано натуральне число N ≤ 10^18.
Вихідні дані
Для кожного числа N з вхідного файлу виведіть у окремому рядку кількість абелевих груп порядку N з точністю до ізоморфізму.