/* Kristoffer Hansen. arnsfelt@daimi.au.dk */

#include <stdio.h>
#include <stdlib.h>

#define MAXP 100000
#define NUMP 10000

int notprime[MAXP];
int primes[NUMP];
int numprimes;

int sieve()
{
  int p,i,n;
  primes[0]=2;
  n=1;
  for (p=3; p<MAXP; p+=2) {
    if (!notprime[p]) {
      for (i=2*p; i<MAXP; i+=p)
	notprime[i]=1;
      primes[n++]=p;
    }
  }
  return n;
}

int sumdigits(int a)
{
  int s;
  s = 0;
  while (a>0) {
    s += a%10;
    a = a/10;
  }
  return s;
}

int main()
{
  int N;
  int i,n,m;
  int s1,s2;

  scanf("%d",&N);
  numprimes=sieve();
  while (N-->0 && scanf("%d",&n)==1) {
    n++;
    for (;;) {
      m=n;
      s1 = sumdigits(m);
      s2=0;
      for (i=0; i<numprimes && primes[i]*primes[i]<=m; i++) {
	while (m%primes[i]==0) {
	  s2+=sumdigits(primes[i]);
	  m/=primes[i];
	}
      }
      if (m!=n) {
	if (m>1)
	  s2+=sumdigits(m);
	if (s1==s2) {
	  printf("%d\n",n);
	  break;
	}
      }
      n++;
    }
  }  
  return 0;
}