题目描述

把质数按从小到大的顺序排列起来，\(2\) 是第 \(1\) 个质数，\(5\) 是第 \(3\) 个质数，依此类推。对于一个给定的大于 \(1\) 的正整数 \(n\)，求 \(n\) 的最大质数因子的序号。例如 \(64\) 的质数因子只有 \(2\)，则答案为 \(1\)；\(65=5×13\)，而 \(13\) 是第 \(6\) 个质数，则答案为 \(6\)。

编程解决这个问题。

格式

输入格式

第一行为正整数 \(t(≤100)\)，表示数据组数；接下来 \(t\) 行，每行一个正整数 \(n(1<n≤10^7)\)。

输出格式

对于每个正整数 \(n\)，输出 \(n\) 最大质数因子的序号。

样例1

输入样例1

2
64
65

输出样例1

1
6

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛\(T2\)

文件IO

freopen("prime.in","r",stdin);
freopen("prime.out","w",stdout);