You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

【题目描述】

​ 小$L$有一个数$n$，他想把他划分成若干个质数的和，求最少能划分成多少个质数的和。

​ 质数指因数只有$1$和它本身的数（$1$不是质数）。

【输入格式】

​ 输入文件名为partition.in。

​ 第一行一个正整数$T$，表示测试点的数目。

​ 第二行至第$T+1$每行一个正整数$n_i$，表示当前小$L$有的数。

【输出格式】

​ 输出文件名为partition.out。

​ 输出共$T$行，每行为一个测试点的答案，即最少可以划分成多少个质数的和。

【样例1】

5
2
4
7
35
18

1
2
1
3
2

【样例解释】

​ $2=2,4=2+2,7=7,35=7+11+17,18=7+11$，可以证明每一个都不会有更少的方案。

【样例2】

​ 见下发文件。

【数据范围】

​ 对于 $30\%$ 的数据，满足 $n_i \leq 10$。

​ 对于 $50\%$ 的数据，满足 $n_i \leq 1000$。

​ 对于 $70\%$ 的数据，满足 $n_i \leq 1,000,000$。

​ 对于 $100\%$ 的数据，满足 $2 \leq n_i \leq 10^{12},1 \leq T \leq 20$。