Abelian Groups
In the city of N in Berlandia, there's a unique tradition. If a girl wants to marry a young man, and he doesn't intend to give her all possible necklaces made of six beads, she must present him with a new abelian group of order N each day. The young man will only agree to give her a new necklace daily, leading to their eventual marriage, once all possible abelian groups have been given. If two abelian groups are isomorphic, they are considered identical, and only one needs to be presented. Athena, a girl in love with a busy programmer named Petya, wants to know how many days she must give him abelian groups before he agrees to give her necklaces.
Let's review the fundamental concepts and facts about abelian groups.
An abelian group is defined as a pair G=(A,*), where A is a set, and * is a binary operation on A. This means that for any two elements a and b in A, there is an element a*b also in A. The following properties, known as the axioms of an abelian group, must be satisfied:
(i) Associativity: For any a, b, c in A, the equation (a*b)*c=a*(b*c) holds.
(ii) There exists an element e in A such that for any a in A, the equations a*e=e*a=a hold.
(iii) For any a in A, there exists a b in A such that the equations a*b=b*a=e hold.
(iv) Commutativity: For any a, b in A, the equation a*b=b*a holds.
A key example of an abelian group is a cyclic group of order n, which consists of the numbers from 0 to n-1 with addition modulo n. It is denoted as Z_n.
The direct sum of two abelian groups G=(A,*) and H=(B,·) is the pair GH = (C,×), where C={(a,b) : a ∈ A, b ∈ B} and (a_1, b_1)×(a_2, b_2) = (a_1 * a_2, b_1 · b_2) for all a_1, a_2 in A and b_1, b_2 in B.
Two groups G=(A,*) and H=(B,·) are called isomorphic if there exists a bijection f from A to B such that f(a_1)·f(a_2)=f(a_1*a_2) for all a_1, a_2 in A.
The fundamental theorem of abelian group theory states that any finite abelian group is isomorphic to the direct sum of some cyclic groups.
The Chinese Remainder Theorem states that Z_mn is isomorphic to Z_mZ_n if and only if m and n are coprime.
These last two statements allow us to describe all abelian groups of order n up to isomorphism.
For example, if n is prime, then all groups of order n are isomorphic to Z_n.
There are 2 non-isomorphic groups of order 4: Z_4 and Z_2Z_2.
There are 3 non-isomorphic groups of order 27: Z_27, Z_9Z_3, and Z_3Z_3Z_3.
There are 4 non-isomorphic groups of order 36: Z_4Z_9, Z_2Z_2Z_9, Z_4Z_3Z_3, and Z_2Z_2Z_3Z_3.
Input
The first line of the input contains a natural number T ≤ 500, representing the number of test cases. Each of the following T lines contains a natural number N ≤ 10^18.
Output
For each number N provided in the input, output the number of abelian groups of order N up to isomorphism on a separate line.