最大的质因数

题目描述

小珅最近学习了如何找一个数的最大质因数，他觉得只是去算最大质因数的话没什么挑战性。于是他现在想找到若干个数的最大质因数在质数表中的位置，即这个质因数是第几个质数。2 是第一个质数，5 是第三个质数，依次类推。

特别地，如果一个数没有质因数，输出 0。

输入描述

第一行一个正整数 T，表示小珅所给出的数字的个数。

接下来 T 行，每行一个数 n。

输出描述

T 行，每行一个非负整数，表示对应的数字 n 的最大质因数是第几个质数。

样例 1

输入：

5
1
2
3
4
5

输出：

0
1
2
1
3

样例 1 解释：1 没有最大质因数；2、3、4、5 的最大质因数是 2、3、2、5，分别是第 1、2、1、3 个质数。

样例 2

输入：

1
123456

输出：

117

输入样例 #3

1
1

输出样例 #3

0

数据范围

• 对于 60% 的数据：T = 1。
• 对于 100% 的数据：1 ≤ T ≤ 10^5，1 ≤ n ≤ 2×10^6。