1. 
/*
* ACM Contest training
* Problem: 10852 - Less Prime
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=20&problem=1793
*
* @author Christoph Goettschkes
* @version 1.0, 11/08/2010
*
* Method : Sieve of Eratosthenes
* Status : Accepted
* Runtime: 0.160
*/

import java.io.*;
import java.util.*;

class Main
{
static List<Integer> primes = new LinkedList<Integer>();

public static void main(String[] args) throws IOException {
sieve(10000);
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

int testCases = Integer.parseInt(reader.readLine().trim());

for (int test = 0 ; test < testCases; test++) {
int cur = Integer.parseInt(reader.readLine());
System.out.println(getP(cur));
}
}

static int getP(int n) {
int max = Integer.MIN_VALUE;
int p = 0;

for (int currentPrime : primes) {
if (currentPrime > n)
break;
if (n % currentPrime >= max) {
max = n % currentPrime;
p = currentPrime;
}
}
return p;
}

public static void sieve(int upperBound) {
long last = 0;

long upperBoundSquareRoot = (int) Math.sqrt(upperBound);
BitSet isComposite = new BitSet(upperBound);

for (long m = 2; m <= upperBoundSquareRoot; m++) {
if (!isComposite.get((int)m)) {
primes.add((int)m);
last = m;
for (long k = m * m; k <= upperBound; k += m) {
isComposite.set((int)k, true);
}
}
}

if (upperBoundSquareRoot == last)
upperBoundSquareRoot++;

for (int m = (int)upperBoundSquareRoot; m <= upperBound; m++) {
if (!isComposite.get(m)) {
primes.add(m);
}
}
}
}