#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define vll vector<long long>
#define ll long long
#define pii pair<int,int>
const ll mod=1e9+7;

ll gcd(ll a,ll b){
    if(a==0) return b;
    else return gcd(b%a,a);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("inputf.txt","r",stdin);
    freopen("output1f.txt","w",stdout);
#endif
    
    int z;
    cin>>z;

    for(int t=1;t<=z;t++){
        ll n;
        cin>>n;
        ll x1=n+1,x2=n+2;
        ll temp=n;
        ll sum=0;
        int digits=0;
        while(temp){
            digits++;
            sum+=temp%10;
            temp/=10;
        }
        if(gcd(sum,n)!=1) cout<<n<<"\n";
        else{
            sum=0;
            temp=n+1;
            while(temp){
                digits++;
                sum+=temp%10;
                temp/=10;
            }
            if(gcd(sum,n+1)!=1) cout<<n+1<<"\n";
            else cout<<n+2<<"\n";
        }
    }
    return 0;
}