Given \(n\) integers, your task is to report for each integer the number of its divisors.

For example, if \(x=18\), the correct answer is \(6\) because its divisors are \(1,2,3,6,9,18\).

Input

• The first input line has an integer \(n\): the number of integers.
• After this, there are \(n\) lines, each containing an integer \(x\).

Output

• For each integer, print the number of its divisors.

Constraints

• \(1 \le n \le 10^5\)
• \(1 \le x \le 10^6\)

Example

Sample input

3
16
17
18

Sample output

5
2
6