Description

        Z国的国王是一个非常爱好数学的国王。一天他对着他的那些大臣说：“ 素数真是一种神奇的正整数， 除了 1和它本身外，不能被其他任何正整数整除 ，2是最小的素数 ，有无穷多个啊 …… 它还有一个美妙的名字：质数， …… 数学多么有趣啊 …… ”。
        Z国今年风调雨顺，百姓丰衣足食 。为了奖励他那帮管理有方的大臣，决定把全部的 N元奖金平均分配给其中的K位大臣，但酷爱数学的国王要求这 K位大臣 每人拿到的奖金必须是个素数。哪个大臣能够解决这数学问题，国王就把奖金给这个大臣和另外的 K-1人。
        大臣们都想自己获 得更多的奖金，所以希望 分得奖金的大臣人数K越少越好。机智的 。机智的大臣请来 了“编程大侠”解决这个问题。国王的间谍得知了 情况后向国王汇报了大臣的行为。国王早就听说“编程大侠”厉害， 于是 决定问 T次问题，来试探一下“编程大侠的真正实力”。

Input Format

输入文件 king.in ：输入从文件中读取，输入共 T+ 1行。
第 1行一个整数T，表示国王问了 T次。
接下来 T行 每行 每一个整数 N，表示国王打算分配给大臣的总奖金。

Output Format

输出文件 king.out ：结果输出到文件中，输出共 T行。
第 i行一个整数 K，表示最少多少位大臣来平分输入中对应的全部奖金。 如果找不到满足国王要求的分配办法，请输出“ 0”（输出时不包含双引号）。

3
3
4
100

1
2
20

Hint

【样例解释】
国王共问了 3次。
第一次国王说：“我们总共有3元奖金”。“编程大侠”说：“最少分配给1位大臣，他可以获得所有奖金，即 3元，因为 3是一个素数 ”。
第二次国王说：“我们总共有4元奖金 ”。“编程大侠”说：“最少分配给2位大臣，他们每人可以获得 2元奖金，因为2是一个素数 ”。
第三次国王说：“我们总共有100元奖金 ”。“编程大侠”说：“最少分配给20 位大臣他们每人可以获得 5元奖金，因为5是一个素数 ”。
【数据范围约定】
50% 的测试点输入数据保证 1≤T≤5，1≤N≤10000
70% 的测试点输入数据保证 1≤T≤10 ，1≤N≤1000000000
100%的测试点输入数据保证1≤T≤10 ，1≤N≤2000000000

Source

模拟 质因数分解