Hãy đếm số lượng thừa số nguyên tố khác nhau trong phân tích thừa số nguyên tố của \(1\) số nguyên dương \(n\).

Input

• Dòng đầu tiên là số lượng test case \(T\ (1 \le T \le 100)\).
• \(T\) dòng tiếp theo mỗi dòng là một số nguyên dương \(n\ (1 \le n \le 10^9)\).

Output

• Với mỗi dòng, đưa ra một số nguyên là số lượng thừa số nguyên tố khác nhau của \(n\).

Example

3
60
128
10000

3
1
2