#include<bits/stdc++.h>
#define ll unsigned long long int
#define N 10000009
using namespace std;
int base[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
int p[N+10];
vector<long int>v;
void prime()
{
int l = sqrt(N);
p[0] = p[1] = 1;
v.push_back(2);
for(int i=4; i<N; i+=2)
p[i] = 1;
for(int i=3; i<N; i+=2)
{
if(p[i] == 0)
{
v.push_back(i);
if(i<=l)
{
for(int j=i*i; j<N; j+=i*2)
p[j] = 1;
}
}
}
}
ll mod(ll a, ll b, ll m)
{
ll r = 0;
a = a%m;
while(b > 0)
{
if(b&1)
r = (r + a)%m;
b = (b >> 1);
a = (a + a)%m;
}
return r;
}
ll power(ll a, ll d, ll n)
{
ll r = 1;
a = a%n;
while(d > 0)
{
if(d&1)
r = mod(r, a, n);
d = (d >> 1);
a = mod(a, a, n);
}
return r;
}
bool miller_rabin(ll n)
{
ll d = n-1;
for(int i=0; i<12; i++)
{
if(base[i] == n)
return true;
if(power(base[i], d, n) != 1)
return false;
}
return true;
}
ll countdivisors(ll n)
{
if(n == 1)
return 1;
ll ans = 1;
for(int i=0; i<v.size(); i++)
{
if((v[i] * v[i] * v[i]) > n)
break;
int cnt = 1;
while(n%v[i] == 0)
{
n = n/v[i];
cnt++;
}
ans = ans * cnt;
}
ll s = sqrt(n);
if(n < N && p[n] == 0)
ans = ans * 2;
else if(n > N && miller_rabin(n) == true)
ans = ans * 2;
else if(s*s == n && p[s] == 0)
ans = ans * 3;
else if(n != 1)
ans = ans * 4;
return ans;
}
int main()
{
prime();
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
while(t--)
{
ll n;
cin >> n;
cout << countdivisors(n) << "\n";
}
return 0;
}
Comments
Post a Comment