摩卡与数学家水獭

题目描述

Moca 非常喜欢水獭，一天，她遇到了一只被难题困扰着的数学家水獭。

对于一个给定的正整数，显然可以把它分解为若干质数的和。数学家水獭想知道，对一个给定的正整数，把它分解为若干质数（可以重复）需要的质数个数最少是多少。

由于这个问题太难了，数学家水獭希望 Moca 编程帮它得到 $5 \times10^6$ 以内的结果。

输入

第一行一个正整数 $n$ ，表示接下来会有 $n$ 组输入，$1 \le n \le 500000$ 。

接下来 $n$ 行，每行一个正整数 $k$ ，代表数学家水獭每次询问的正整数，有 $2\le k \le 5\times10^6$ 。

输出

输出 $n$ 行，每行一个正整数，代表对应输入的正整数被分解的最少的质数个数。

输入样例

4
3
9
12
27

输出样例

1
2
2
3

样例解释

对于 $3$ ，质数个数最少的分解为 $3 = 3$ ，只需要 $1$ 个质数。

对于 $9$ ，质数个数最少的分解为 $9 = 2 + 7$ ，需要 $2$ 个质数。

对于 $12$ ，质数个数最少的分解为 $12 = 5 + 7$ ，需要 $2$ 个质数。

对于 $27$ ，质数个数最少的一种分解为 $27 = 3 + 7 + 17$ ，需要 $3$ 个质数。

Author：Moca