Background

无聊的 Jerrlee 让你写起了无聊的 Decomposition Factor ，~~还要求用递归写~~......

Description

Jerrlee 有n个正整数a，要分解成若干个正整数的乘积，即a = a1 * a2 * ... * ax，并且1 < a1 <= a2 <= ... <= ax，问分解种数最少有多少。

Format

Input

第1行是测试数据的组数n，后面有n个数。每组测试数据为一个正整数a (1 <= n <= 10^7 )。

Output

n行，每行输出对应一个输入。输出是一个正整数，为最少分解种数。

Sample 1

Input

2
2 20

Output

1
4

Hint

注意a=a也是一种分解，不用递归扣分！