Algorithms and Data Structures

Number of divisors for many numbers

For each given integer n, you are asked to find the number of divisors of n.

Input

The first line of the input contains a single integer t (2 ≤ n ≤ 1000) the number of test cases.

The next t lines contain t integers (1 ≤ ≤ ).

Output

The program should print the number of divisors for each on a separate line.

Examples

Input

Output

3
8
23
74

4
2
4

Constraints

Time limit: 3 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue