Subtract or Divide

题意翻译

### 题目描述 Ridbit 有一个数 $n$. Ta 每次可以进行以下一种操作： - 除以数 $n$ 的一个因子（$n$ 本身除外）。 - 如果 $n$ 大于 $1$ ,则可以将 $n$ 减去 $1$ 。 问：Ta 最少要几次操作使 $n$ 变为 $1$. ### 输入格式 第一行，一个数 $t$ （$1 \le t \le 1000$）表示测试用例数量。 接下来 $t$ 行，每行一个数 $n$ 。 ### 输出格式 对于每个测试用例，输出至少要几次操作才能把 $n$ 变成 $1$ 。 translate by @[一啦啦啦一](https://www.luogu.com.cn/user/109222)

题目描述

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 $