1. 
import java.util.Scanner;

/**
* Angewandte Mathematik, SS11
* Problem 11960 Divisor Game
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2520
*
* @author Benedikt ZĘnnchen
* @author Erik Wenzel
* @version 1.0, 29/04/2011
*
* Method : Combinatorics, Memorizing
* Status : Accepted
* Runtime:
*/
public class Main
{
static int[] primes = new int[1000];
static int[] divs = new int[1000001];
public static void main(String[] args)
{
primes = getPrime(primes);
for(int i = 0; i < divs.length; i++)
{
divs[i] = countDiv(i);
}


Scanner sc = new Scanner(System.in);
int cases = sc.nextInt();

for (int i = 0; i < cases; i++)
{
int result = sc.nextInt();
int currentMaxDiv = 2;
for (int j = result; j > 3; j--)
{
int tmpDivs = divs[j];
if (tmpDivs > currentMaxDiv)
{
currentMaxDiv = tmpDivs;
result = j;
}
}
System.out.println(result);
}
}

/**
* Bestimmt ob eine ganze Zahl eine Primzahl ist. (schleifen-lĘsung)
* @param n ganze zahl
* @return true wenn n eine Primzahl ist, sonst false
*/
public static int[] getPrime(int[] primes)
{
primes[0] = 2;
primes[1] = 3;
int counter = 2;
boolean isPrime = false;
int j = 2;

while(counter < primes.length)
{
j++;
if (j % 2 == 0)
{
continue;
}
for (int i = 3; i < j; i += 2)
{
if (j % i == 0)
{
isPrime = false;
break;
}
isPrime = true;
}
if (isPrime)
{
primes[counter++] = j;
}
}
return primes;
}

/**
* counts the divisors in n
* @param n
* @return amount of divsors
*/
public static int countDiv(int n)
{
int r = 1, j;
int i = 0;
while (n > 1)
{
if (isPrime(n))
{
r *= 2;
break;
}
while (i < primes.length && n % primes[i] != 0)
{
i++;
}
if(i >= primes.length)
{
return 2;
}

j = 0;
while (n % primes[i] == 0)
{
n /= primes[i];
j++;
}
r *= (j + 1);
}
return r;
}

/**
* checks based on an array of primes if the number is a prime
* this only works in the range of the array!
* @param n number to check
* @return true if its a prime else false
*/
public static boolean isPrime(long n)
{
for (int i = 0; i < primes.length; i++)
{
if (primes[i] == n)
{
return true;
}
else if (primes[i] > n)
{
break;
}
}
return false;
}
}


2.


/**
* Angewandte Mathematik, SS11
* Problem: 11960 Divisor Game
* Link:
*
* @author Schramm, Felix
* @author Vogel, Johannes
* @version 1.0, 06/27/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.976
*/

import java.util.Scanner;

public class Main {


public static void main(String[] args) {
Scanner input = new Scanner(System.in);
StringBuffer output = new StringBuffer();
int cases = input.nextInt();
int[] million = new int[1000001];
million[1]++;
int temp;
for(int i=2; i<=1000000; i++){
temp=i;
while(temp<=1000000){
million[temp]++;
temp+=i;
}
}
int[] nillion = new int[1000001];
int high,result;
high = 0;
result = 0;
for(int i = 0; i<=1000000; i++){
if(million[i]>=high){
high = million[i];
result=i;
}
nillion[i]=result;
}
int n;
for(int i = 0; i<cases;i++){
n = input.nextInt();
output.append(nillion[n]+"\n");
}
System.out.print(output);
}

}