1. 

/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #10042 (Smith Numbers)
* http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=983
*
* @author Marcel Sachse
* @author Fabian Seidl
* @version 1.0, 31.03.2009
*
* Status : Accepted
* Runtime: 1.050
*/


import java.io.BufferedInputStream;
import java.util.Scanner;


public class Main {

public static void main(String[] args)

{
BufferedInputStream bin = new BufferedInputStream(System.in);
Scanner scanner = new Scanner(bin);

int counter = scanner.nextInt();
for (int i=0;i<counter;i++)
{
int zahl=scanner.nextInt();
while(true)
{
zahl++;
// vergleichen der Quersummen der zahl und der primzahlfakturen
if(qSum(zahl)==qPrimFakt(zahl))break;
}
System.out.println(zahl);
}
scanner.close();
}

private static int qPrimFakt(int zahl)
{
int i=2;
int sum=0;
// es gibt nur primzahlfakturen unter der wurzel der zahl
double abbruch = Math.sqrt(zahl);
while(zahl>1)
{
while(true)
{
if(i>abbruch)i=zahl;
// überprüfen ob eine zahl teiler und primzahl ist
if( (zahl%i)==0 && isPrim(i))
{
zahl/=i;
break;
}
i++;
}
//quersumme der primfaktoren

//wenn die summe null ist und i gleich ein haießt das,
//das die zahl nur einen faktur hat und zwar sich selber
if (sum==0 && zahl==1)sum=-1;
// aufaddieren der quersumme der primfakturen
else sum+=qSum(i);
}
return sum;
}
// quersumme berechnen
public static int qSum(int zahl)
{
int sum =0;
while(zahl>0)
{
sum+= zahl%10;
zahl/=10;
}
return sum;

}

private static boolean isPrim(int number)
{

if (number < 2) {
return false;
//überprüfen ob es die primzahl 2 ist
} else if (number == 2)
{
return true;
} else {
// überprüfen ob die zahl ein fielfaches der 2 ist
if (number % 2 == 0) {
return false;
}
// alle ungeraden zahlen ab 3 prüfen bis zur wurzel der zahl
for (int i = 3; i <= Math.sqrt(number); i = i + 2)
{
//Teilertest
if (number % i == 0)
{
return false;
}
}
return true;
}
}
}