using namespace std;
#include <bits/stdc++.h>

int main() {
	int n = 0;
        // first input a number indicates the number of test cases;
	cin >> n;
	vector<int> nums(n, 0);
	int maxVal = 0;
        // get n test cases;
	for (int i = 0; i < n; ++i)
	{
		cin >> nums[i];
		maxVal = max(maxVal, nums[i]);
	}
	//unordered_map<int, int> primes;
	vector<int> primes;
	primes.reserve(maxVal);
	vector<int> aux(maxVal + 1, true);
	aux[0] = false;
	aux[1] = false;
	for (int i = 2; i < maxVal; ++i)
	{
		if (aux[i])
		{	
			primes.push_back(i);
			for (int j = 2; j <= maxVal / i; ++j)
			{
				aux[i * j] = false;
			}
		}
	}
	for (int& num : nums)
	{
		vector<int> dp(num + 1, 0);
		for (int i = 2; i <= num; ++i)
		{
			if (aux[i])
			{
				dp[i] = 1;
			}
			else
			{
				dp[i] = dp[i - 1] + 1;
				auto it = upper_bound(primes.begin(), primes.end(), i);
				--it;
				do
				{
					if (i % *it == 0)
					{
						dp[i] = min(dp[i], dp[i / *it] + 1);
						break;
					}
					--it;
				} while (it != primes.begin());
			}
		}
		cout << dp[num] << endl;
	}
	return 0;
}