CF1451A 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)

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 $