CF1451A.Subtract or Divide

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

Ridbit 从一个整数 $n$ 开始。

在一次操作中，他可以执行以下操作之一：

• 将 $n$ 除以其某个真因子（proper divisor），或
• 若 $n > 1$，则将 $n$ 减去 $1$。

一个数的真因子是指该数的因子中不包含其自身的那些因子。例如，$1$、$2$、$4$、$5$ 和 $10$ 是 $20$ 的真因子，但 $20$ 本身不是。

Ridbit 至少需要多少次操作才能将 $n$ 减小到 $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$).

第一行包含一个整数 $t$（$1 \leq t \leq 1000$）—— 表示测试用例的数量。

每个测试用例仅有一行，包含一个整数 $n$（$1 \leq n \leq 10^9$）。

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

对于每个测试用例，输出将 $n$ 减少到 $1$ 所需的最少移动次数。

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$

对于示例中的测试用例，$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$