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

Input

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

Output

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

Examples

Input 1

10
1
2
3
4
5
6
7
8
9
10

Output 1

1
2
2
3
2
5
2
4
3
5