Background

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

Z 国今年风调雨顺，百姓丰衣足食。为了奖励他那帮管理有方的大臣，他决定把全部的 $N$ 元奖金平均分配给其中的 $K$ 位大臣，但酷爱数学的国王要求这 $K$ 位大臣每人拿到的奖金必须是个素数。哪个大臣能够解决这个数学问题，国王就把奖金给这个大臣和另外的 $K-1$ 人。

大臣们都想自己获得更多的奖金，所以希望分得奖金的大臣人数 $K$ 越少越好。机智的大臣请来了“编程大侠”来帮忙解决这个问题。国王的间谍得知了这个情况后向国王汇报了大臣的行为。国王早就听说“编程大侠”的厉害，于是决定问 $T$ 次这个问题，来试探一下 “编程大侠”的真正实力。

Input

输入共 $T+1$ 行。

第 $1$ 行一个整数 $T$，表示国王问了 $T$ 次。 接下来 $T$ 行每行一个整数 $N$，表示国王打算分配给大臣的总奖金。

Output

输出共 $T$ 行。

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

Samples

3 
3 
4 
100

1
2
20

Limitation

【样例解释】 国王共问了 $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$