Ridbit 以整数 $$$n$$$ 开头。
一招之内,他可以执行以下操作之一:
- 将 $$$n$$$ 除以它的真因数之一,或者
- 如果 $$$n$$$ 大于 $$$1$$$,则从 $$$n$$$ 中减去 $$$1$$$。
真除数是一个数的除数,不包括它本身。例如,$$$1$$$、$$$2$$$、$$$4$$$、$$$5$$$ 和 $$$10$$$ 是 $$$20$$$ 的真因数,但 $$$20$$$ 本身不是。
Ridbit 需要最少移动多少步才能将 $$$n$$$ 减少到 $$$1$$$?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。
每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^9$$$)。
输出
对于每个测试用例,输出将 $$$n$$$ 减少到 $$$1$$$ 所需的最小移动次数。
示例
输入 #1
6 1 2 3 4 6 9
输出 #1
0 1 2 2 2 3
注意
对于示例中的测试用例,按顺序使用以下操作可以将 $$$n$$$ 减少为 $$$1$$$
$$$1$$$
$$$2 \xrightarrow{} 1$$$
$$$3 \xrightarrow{} 2 \xrightarrow{} 1$$$
$$$4 \xrightarrow{} 2 \xrightarrow{} 1$$$
$$$6 \xrightarrow{} 2 \xrightarrow{} 1$$$
$$$9 \xrightarrow{} 3 \xrightarrow{} 2\xrightarrow{} 1$$$