简单模拟即可。

• 考虑 $n=1$ 直接不用变
• 考虑 $n=2$ 减 $1$
• 考虑 $n=3$ 减 $2$

之后的 $n$ 我们要想办法把它变到 $2$ 或者 $3$，然后就可以一步到位了。

考虑 $n\gt3$ 并且 $n$ 是偶数，我们可以找到他的一个因数 $2$，那么我们可以一步变到 $2$，剩下再减 $1$就行了。

考虑 $n\gt3$ 并且 $n$ 是奇数，我们想想他能变为 $2,3$ 的可能情况：

• 只要是 $3$ 的倍数，我们直接变为 $3$，再减 $2$。
• 不是 $3$ 的倍数，它就是一个奇数，那么我们先给它减 $1$ 就变成偶数了，所以就是偶数的那种情况啦。

时间复杂度 $O(1)$

#include <bits/stdc++.h>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;

void solve() {
	int n;
	std::cin >> n;
	if (n == 1) {
		std::cout << 0 << '\n';
	} else if (n <= 3) {
		std::cout << 1 << '\n';
	} else {
		if (n % 2 == 0) {
			std::cout << 2 << '\n';
		} else {
			if (n % 3 == 0) {
				std::cout << 2 << '\n';
			} else {
				std::cout << 3 << '\n';
			}
		}
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int t; 
	std::cin >> t;
	while (t --) {
		solve();
	}

	return 0;
}