CF1451A.Subtract or Divide

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

Ridbit starts with an integer $n$ .

In one move, he can perform one of the following operations:

divide $n$ by one of its proper divisors, or
subtract $1$ from $n$ if $n$ is greater than $1$ .

A proper divisor is a divisor of a number, excluding itself. For example, $1$ , $2$ , $4$ , $5$ , and $10$ are proper divisors of $20$ , but $20$ itself is not.

What is the minimum number of moves Ridbit is required to make to reduce $n$ to $1$ ?

输入格式

The first line contains a single integer $t$ ( $1 \leq t \leq 1000$ ) — the number of test cases.

The only line of each test case contains a single integer $n$ ( $1 \leq n \leq 10^9$ ).

输出格式

For each test case, output the minimum number of moves required to reduce $n$ to $1$ .

输入输出样例

输入#1
```
6
1
2
3
4
6
9
```
输出#1
```
0
1
2
2
2
3
```

说明/提示

For the test cases in the example, $n$ may be reduced to $1$ using the following operations in sequence

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

首页