Description

输入若干个数，每个数位一个 int 类型的整数 x，需要返回这个数 x 所拥有的不同的质因数的个数。

例如数字 252 ，分解质因数为 252=2×2×3×3×7 ，那么它所拥有的不同质因数为 2,3,7 ，个数为 3 。

Input Format

第一行一个整数 q ，表示有 q 组询问。

接下去 q 行，每行包含一个正整数 x，表示一次询问。

Output Format

共 q 行，包含一个整数，表示一组询问的答案。

2
48
252

2
3

Hint

数据范围

1≤q≤1000 2≤x≤10^6^