G. An Easy Math Problem
time limit per test
1 second
memory limit per test
128 megabytes
input
standard input
output
standard output

You are given an integer $$$n$$$. For each $$$p\leq q$$$, where $$$pq \mid n$$$, denote $$$r=\frac pq$$$. Find the number of different values of $$$r$$$.

Input

The first line of the input contains one integer $$$q$$$ ($$$1\leq q\leq 2000$$$), denoting the number of test cases. The next $$$q$$$ lines each contain one integer $$$n$$$ ($$$1\leq n\leq10^{10}$$$).

Output

For each test case, print one line: an integer, the number of different values of $$$r$$$.

Example
Input
10
1
2
3
4
5
6
7
8
9
10
Output
1
2
2
3
2
5
2
4
3
5