/* package codechef; // don't place package name! */

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

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Scanner sc=new Scanner(System.in);
		int test_case=sc.nextInt();
		while(test_case-- >0){
		    long cupcake=sc.nextLong();
		    if(cupcake>1)
		        System.out.println(maxCupcakes(cupcake));
		    else if(cupcake==1)
		        System.out.println(1);
		    else if(cupcake==0)
		        System.out.println(0);
		}
	}
	private static long maxCupcakes(long cupcake){
	    long result=0;
	    long temp=0;
	    for(long i=2;i<=cupcake;i++){
	        if(isPrime(i)){
	            temp=cupcake%i;
	        }
	        result=Math.max(temp,result);
	    }
	    return cupcake-result;
	}
	private static boolean isPrime(long max_num){
	   boolean isPrime = true;
	   for (long num = 2; num <= max_num; num++)
        {
            for (long i=2; i <= num/2; i++)
            {
                if ( num % i == 0)
                {
                    isPrime = false;
                    break;
                }
            }
        }
        return isPrime;
	}
}