NUMDIV - Number of divisors

In a class the teacher gave all the acm icpc aspirants a challenge on number theory. They could not solve it so they need your help. Help the students to solve this task.

The task that you will be given a number N. You have to calculate the number of positive integral divisors of that number. 

(1 and N are considered to be the divisors of N)

Input

There are T test cases.(1≤T≤102).

First you will be given the number T. Then T numbers follow.

(numbers are space separated)

next line contains T numbers N (1 ≤ N ≤ 10^18).

Output

In each line print the number of divisors of a number N.

Example

Input:
3
6 24 100

Output:
4
8
9

Added by:aashrayagarwal
Date:2016-09-29
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU

hide comments
2022-03-31 19:32:49
AC in 0.02s :)
2020-07-25 14:06:46
Try to do this with O(n^1/3) ,using miller rabin test,that will
accepted in one go
2019-06-21 09:57:11
Beware of overflows in miller rabin function. Useful test case:
1
1000000000000000057
answer:
4

2920910506223 => is a prime


Last edit: 2019-06-21 09:58:57
2018-12-03 21:04:36
need code ...anyone can help?please
2017-05-26 03:27:56
@aashray my code is showing WA, where I am wrong ?
2017-04-06 19:14:03
ac in one go
learned a lot
use prime factorization in N^1/3 and Miller–Rabin primality test :)
2017-02-15 18:11:45
@holmesherlock YES
2017-02-07 08:02:02
can there be a prime in the test cases greater than 10^12 ..just asking..
2017-01-18 10:38:15
@kira28 you dont have to find the exact value of large prime numbers..all you need to do is to compute their powers as you are required to calculate the number of divisors...(think about some probabilistic approach)
2016-12-28 09:02:28
@aashray : How to factorise semi-primes which are product of two very large primes??
any hints because i'm getting TLE in such cases :/


Last edit: 2016-12-28 18:12:58
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.