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

hide comments
panny: 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

smso: 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
elmer_fudd: 2018-12-03 21:04:36

need code ...anyone can help?please

vivek4434: 2017-05-26 03:27:56

@aashray my code is showing WA, where I am wrong ?

ashu121: 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 :)

aashray: 2017-02-15 18:11:45

@holmesherlock YES

holmesherlock: 2017-02-07 08:02:02

can there be a prime in the test cases greater than 10^12 ..just asking..

aashray: 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)

kira28: 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
aashray: 2016-10-31 15:00:32

@hamhom2008 try to optimize the code..your solution seems to be a brute one.


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