Абелевы группы
В стране Берляндии в городе 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 с точностью до изоморфизма.