В стране Берляндии в городе \textbf{N} есть такая традиция. Если девушка хочет выйти замуж за молодого человека, а у него в планах нет дарить ей все возможные ожерелья из шести бусинок, то она должна каждый день дарить ему одну новую абелеву группу порядка \textbf{N}. И только когда все возможные абелевы группы подарены, молодой человек согласится каждый день дарить ей одно новое ожерелье из шести бусинок, и в конце концов они поженятся. При этом если две абелевы группы изоморфны, то они считаются одинаковыми и дарить надо только одну из них. Девушка по имени Афина влюбилась в одного очень занятого программиста по имени Петя. Теперь она хочет узнать сколько дней ей нужно дарить ему абелевы группы, прежде чем он согласится дарить ей ожерелья. Напомним основные понятия и факты касательно абелевых групп. Абелева группа это пара \textbf{G=(A,*)}, где \textbf{A} - это некоторое множество, а \textbf{*} - это бинарная операция на \textbf{A}, то есть любым двум элементам \textbf{a} и \textbf{b} из \textbf{A} ставится в соответствие элемент \textbf{a*b}, также принадлежащий \textbf{A}. При этом должны быть выполнены следующие свойства, называемые аксиомами абелевой группы: \includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg} (i) \textit{Ассоциативность}: для любых \textbf{a}, \textbf{b}, \textbf{c} \textbf{A} выполнено равенство \textbf{(a*b)*c=a*(b*c)}. \includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg} \includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg} (ii) Существует \textbf{e} \textbf{A} такой, что для любого \textbf{a} \textbf{A} выполнены равенства \textbf{a*e=e*a=a}. \includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg} \includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg} (iii) Для любого \textbf{a} \textbf{A} существует \textbf{b} \textbf{A} такой, что выполнены равенства \textbf{a*b=b*a=e}. \includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg} (iv) \textit{Коммутативность}: для любых \textbf{a}, \textbf{b} \textbf{A} выполнено равенство \textbf{a*b=b*a}. Важным примером абелевой группы является циклическая группа порядка \textbf{n}: множество чисел от \textbf{0} до \textbf{n-1} с операцией сложения по модулю \textbf{n}. Она обозначается как \textbf{Z_n}. \includegraphics{https://static.e-olymp.com/content/7e/7e838c0f60f64deef9d13ec9a874ce43b20530ea.jpg} \includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg} \includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg} \includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg} \includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg} Прямой суммой двух абелевых групп \textbf{G=(A,*)} и \textbf{H=(B,·)} называется пара \textbf{GH} =\textbf{(C,×)}, \textbf{C=\{(a,b) : aA, bB\}} и (\textbf{a_1}, \textbf{b_1})×(\textbf{a_2}, \textbf{b_2}) = (\textbf{a_1} * \textbf{a_2}, \textbf{b_1} · \textbf{b_2}) для всех \textbf{a_1}, \textbf{a_2} \textbf{A} и \textbf{b_1}, \textbf{b_2} \textbf{B}. \includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg} Две группы \textbf{G=(A,*)} и \textbf{H=(B,·)} называются изоморфными, если существует взаимно однозначное отображение \textbf{f} из \textbf{A} на \textbf{B} такое, что \textbf{f(a_1)·f(a_2)=f(a_1*a_2)} для всех \textbf{a_1}, \textbf{a_2} \textbf{A}. Фундаментальная теорема теории абелевых групп утверждает, что любая конечная абелева группа изоморфна прямой сумме некоторых циклических групп. \includegraphics{https://static.e-olymp.com/content/7e/7e838c0f60f64deef9d13ec9a874ce43b20530ea.jpg} Китайская теорема об остатках утверждает, что \textbf{Z_mn} изоморфно \textbf{Z_mZ_n} тогда и только тогда, когда \textbf{m} и \textbf{n} взаимно просты. Последние два утверждения позволяют описывать все абелевы группы порядка \textbf{n} с точностью до изоморфизма. Например, если \textbf{n} - простое, то все группы порядка \textbf{n} изоморфны \textbf{Z_n}. \includegraphics{https://static.e-olymp.com/content/7e/7e838c0f60f64deef9d13ec9a874ce43b20530ea.jpg} Существуют \textbf{2} неизоморфные группы порядка \textbf{4}: \textbf{Z_4} и \textbf{Z_2Z_2}. \includegraphics{https://static.e-olymp.com/content/7e/7e838c0f60f64deef9d13ec9a874ce43b20530ea.jpg} \includegraphics{https://static.e-olymp.com/content/7e/7e838c0f60f64deef9d13ec9a874ce43b20530ea.jpg} \includegraphics{https://static.e-olymp.com/content/7e/7e838c0f60f64deef9d13ec9a874ce43b20530ea.jpg} Существуют \textbf{3} неизоморфные группы порядка \textbf{27}: \textbf{Z_27}, \textbf{Z_9Z_3} и \textbf{Z_3Z_3Z_3}. \includegraphics{https://static.e-olymp.com/content/7e/7e838c0f60f64deef9d13ec9a874ce43b20530ea.jpg} \includegraphics{https://static.e-olymp.com/content/7e/7e838c0f60f64deef9d13ec9a874ce43b20530ea.jpg} \includegraphics{https://static.e-olymp.com/content/7e/7e838c0f60f64deef9d13ec9a874ce43b20530ea.jpg} \includegraphics{https://static.e-olymp.com/content/7e/7e838c0f60f64deef9d13ec9a874ce43b20530ea.jpg} \includegraphics{https://static.e-olymp.com/content/7e/7e838c0f60f64deef9d13ec9a874ce43b20530ea.jpg} \includegraphics{https://static.e-olymp.com/content/7e/7e838c0f60f64deef9d13ec9a874ce43b20530ea.jpg} \includegraphics{https://static.e-olymp.com/content/7e/7e838c0f60f64deef9d13ec9a874ce43b20530ea.jpg} \includegraphics{https://static.e-olymp.com/content/7e/7e838c0f60f64deef9d13ec9a874ce43b20530ea.jpg} Существуют \textbf{4} неизоморфные группы порядка \textbf{36}: \textbf{Z_4Z_9}, \textbf{Z_2Z_2Z_9}, \textbf{Z_4Z_3Z_3} и \textbf{Z_2Z_2Z_3Z_3}. \InputFile В первой строке входного файла задано натуральное число \textbf{T} ≤ \textbf{500}, количество тестов. В каждой из последующих \textbf{T} строк задано натуральное число \textbf{N} ≤ \textbf{10^18}. \OutputFile Для каждого числа \textbf{N} из входного файла выведите в отдельной строке количество абелевых групп порядка \textbf{N} с точностью до изоморфизма.