题目描述

Z国的国王非常爱好数学。一天，他对大臣们说：“素数真是一种神奇的正整数，除了1和它本身外，不能被其他任何正整数整除，2是最小的素数，有无穷多个啊……它还有一个美妙的名字：质数，……数学多么有趣啊……”

Z国今年风调雨顺，百姓丰衣足食。为了奖励管理有方的大臣，国王决定把全部的N元奖金平均分配给其中的K位大臣，但酷爱数学的国王要求这K位大臣每人拿到的奖金必须是个素数。大臣们希望分得奖金的人数K越少越好。

国王决定问T次这个问题，来试探“编程大侠”的实力。

输入格式

输入共T+1行。 第1行一个整数T，表示国王询问的次数。 接下来T行，每行一个整数N，表示国王打算分配的总奖金。

输出格式

输出共T行。 第i行一个整数K，表示最少需要多少位大臣来平分对应的奖金。如果找不到满足要求的分配办法，请输出0。

样例输入

3
3
4
100

样例输出

1
2
20

提示

样例解释

国王共问了3次：

• 第一次，奖金3元：最少1位大臣，因为3是素数。
• 第二次，奖金4元：最少2位大臣，每人2元（2是素数）。
• 第三次，奖金100元：最少20位大臣，每人5元（5是素数）。

数据范围

• 50%的测试点：1≤T≤5，1≤N≤10000
• 70%的测试点：1≤T≤10，1≤N≤10^9
• 100%的测试点：1≤T≤10，1≤N≤2×10^9