#include <iostream>
#include <cmath>
using namespace std;

inline int sumaDigitos(int num) {
    // calcula la suma de los dígitos de un nro
	int suma = 0;
	while (num > 0) {
		suma += num % 10;
		num /= 10;
	}
	return suma;
}

inline bool smith(int num, int p[]) {
    int n = num;
    int sumDigs = sumaDigitos(n);
	int i = 0;      // indice para recorrer el arreglo p[]
	int suma = 0;   // suma de los digitos de la descomposición en primos
	int raiz = (int) sqrt(n);

	while (n > 1 && p[i] <= raiz)
		if (n % p[i] == 0) {    // si es divisible por un primo
			suma += sumaDigitos(p[i]);
			if (suma > sumDigs) // si me paso, devuelvo false
                return false;
			n /= p[i];
		} else
			i++;    // pruebo con el siguiente primo

    // si num es primo, devuelvo false (por definición)
    if (n == num)
        return false;

	// después del while, n o es primo o vale 1
    if (n > 1)
        suma += sumaDigitos(n);

    return suma == sumDigs;
}

inline void calcPrimos(int p[]) {  // calculo los primos hasta el 31627
	p[0]=2;
	p[1]=3;
	int cantPrimos = 2;
	for (int i = 5; i <= 31627; i+=2) {
		bool primo = true;
		int raiz = (int) sqrt(i);
		for (int j = 1; primo && p[j] <= raiz; j++)
			if (i % p[j] == 0)
				primo = false;
		if (primo)
			p[cantPrimos++] = i;
	}
}

int main() {
    int p[3402];	// 3402 = cantidad de primos hasta 31627
                    // 31627 = primer primo mayor a sqrt(10^9)
                    // 10^9 = mayor input
	calcPrimos(p);
	int n, num;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> num;
		while (!smith(++num, p));
        cout << num << endl;
	}
	return 0;
}