﻿
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <utility>
#include <string.h>
#include <string>
#include <math.h>
#include <stack>
#include <set>
#include <map>
#include <queue>
#include <iterator> 
#include <iostream>
#include <vector>
#include <algorithm> 
#include <unordered_map> 
#include <bitset>
typedef long long ll;
using namespace std;
const long long INF = 1ll << 32;
const double pi = acos(-1);
int dc[] = { 0,0,1,-1 }, dr[] = { 1,-1,0,0 };
void yes() {
	printf("YES\n");
	//exit(0);
	return;
}
void no() {
	printf("NO\n");
	//exit(0);
	return;
}
void line() {
	printf("\n");
	return;
}

int main() {
	//freopen("input.txt", "r", stdin);
	int t;
	scanf("%d", &t);
	while (t--) {
		int n;
		scanf("%d", &n);
		int ans = n - 1;
		for (int i = 2; i*i <= n; i++) {
			if (n%i == 0) {
				ans = min(ans, i);
				break;
			}
		}
		n--;
		for (int i = 2; i*i <= n; i++) {
			if (n%i == 0) {
				ans = min(ans, i+1);
				break;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}