Description

• $q$ 次询问，每次给一个正整数 $n$，问 $n$ 有多少个因子。

Format

Input

第一行一个数字 $q$，后面 $q$ 行，每行一个整数 $n$

Output

$q$ 行，每行一个答案。

Samples

5
5
15
840
2022
2000100

2
4
32
8
72

Limitation

• $1≤q≤10^6$
• $1≤n≤10^8$
• 请使用 $O(q\ log\ n)$ 的时间复杂度完成本题。

3s, 512MiB for each test case.