← 返回题目列表

Codeforces · 1451/A

A. 减法或除法

中文机器翻译题面 查看原题

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$$$