#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
using namespace std;
int waga(int n)
{
n++;
int ln=0,lp=0;
for(int i=1; i<=n; i++)
{
if(n%i==0)
{
if(i%2==0) lp++;
if(i%2!=0) ln++;
}
}
if(lp!=ln) waga(n);
else return n;
}
string w(string a)
{
string b;
if(a.size()==1) b=a.substr(a.size()-1,1);
if(a.size()==2) b=a.substr(a.size()-2,2);
if(a.size()>=3) b=a.substr(a.size()-3,3);
int x=stoi(b);
int y=waga(x);
return to_string(y);
}
string math(string a)
{
string b=w(a);
string zero1="0";
string zero2="00";
string zero3="000";
if(a.size()==1) a.replace(a.size()-1,1,zero1);
if(a.size()==2) a.replace(a.size()-2,2,zero2);
if(a.size()>=3) a.replace(a.size()-3,3,zero3);
int pa=a.size()-1;
int pb=b.size()-1;
string wynik;
int p=0;
while(pa>=0 || pb>=0)
{
int ca,cb,w;
if(pa>=0) ca=a[pa]-48;
else ca=0;
if(pb>=0) cb=b[pb]-48;
else cb=0;
w=ca+cb+p;
wynik="0"+wynik;
wynik[0]=48+w%10;
p=w/10;
pa--;
pb--;
}
if(p) wynik="1"+wynik;
return wynik;
}
int main()
{
string N;
vector <string> tab;
int C,l=0;
cin>>C;
if(C>=1 && C<=100)
{
while(C--)
{
cin>>N;
if(N.size()<=200)
{
string wynik=math(N);
cout<<wynik<<endl;
}
}
}
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3N0ZGxpYj4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPHZlY3Rvcj4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgd2FnYShpbnQgbikKewogICAgbisrOwogICAgaW50IGxuPTAsbHA9MDsKCgogICAgZm9yKGludCBpPTE7IGk8PW47IGkrKykKICAgIHsKICAgICAgICBpZihuJWk9PTApCiAgICAgICAgewogICAgICAgICAgICBpZihpJTI9PTApIGxwKys7CiAgICAgICAgICAgIGlmKGklMiE9MCkgbG4rKzsKICAgICAgICB9CgogICAgfQogICAgaWYobHAhPWxuKSB3YWdhKG4pOwogICAgZWxzZSByZXR1cm4gbjsKCn0KCgpzdHJpbmcgdyhzdHJpbmcgYSkKewogICAgc3RyaW5nIGI7CiAgICBpZihhLnNpemUoKT09MSkgYj1hLnN1YnN0cihhLnNpemUoKS0xLDEpOwogICAgaWYoYS5zaXplKCk9PTIpIGI9YS5zdWJzdHIoYS5zaXplKCktMiwyKTsKICAgIGlmKGEuc2l6ZSgpPj0zKSBiPWEuc3Vic3RyKGEuc2l6ZSgpLTMsMyk7CgogICAgaW50IHg9c3RvaShiKTsKICAgIGludCB5PXdhZ2EoeCk7CgogICAgcmV0dXJuIHRvX3N0cmluZyh5KTsKCn0KCnN0cmluZyBtYXRoKHN0cmluZyBhKQp7CgogICAgc3RyaW5nIGI9dyhhKTsKICAgIHN0cmluZyB6ZXJvMT0iMCI7CiAgICBzdHJpbmcgemVybzI9IjAwIjsKICAgIHN0cmluZyB6ZXJvMz0iMDAwIjsKICAgIGlmKGEuc2l6ZSgpPT0xKSBhLnJlcGxhY2UoYS5zaXplKCktMSwxLHplcm8xKTsKICAgIGlmKGEuc2l6ZSgpPT0yKSBhLnJlcGxhY2UoYS5zaXplKCktMiwyLHplcm8yKTsKICAgIGlmKGEuc2l6ZSgpPj0zKSBhLnJlcGxhY2UoYS5zaXplKCktMywzLHplcm8zKTsKCiAgICBpbnQgcGE9YS5zaXplKCktMTsKICAgIGludCBwYj1iLnNpemUoKS0xOwoKICAgIHN0cmluZyB3eW5pazsKICAgIGludCBwPTA7CgogICAgd2hpbGUocGE+PTAgfHwgcGI+PTApCiAgICB7CiAgICAgICAgaW50IGNhLGNiLHc7CgogICAgICAgIGlmKHBhPj0wKSBjYT1hW3BhXS00ODsKICAgICAgICBlbHNlIGNhPTA7CiAgICAgICAgaWYocGI+PTApIGNiPWJbcGJdLTQ4OwogICAgICAgIGVsc2UgY2I9MDsKCiAgICAgICAgdz1jYStjYitwOwoKICAgICAgICB3eW5paz0iMCIrd3luaWs7CiAgICAgICAgd3luaWtbMF09NDgrdyUxMDsKCiAgICAgICAgcD13LzEwOwoKICAgICAgICBwYS0tOwogICAgICAgIHBiLS07CiAgICB9CiAgICBpZihwKSB3eW5paz0iMSIrd3luaWs7CgogICAgcmV0dXJuIHd5bmlrOwp9CgoKCmludCBtYWluKCkKewogICAgc3RyaW5nIE47CiAgICB2ZWN0b3IgPHN0cmluZz4gdGFiOwogICAgaW50IEMsbD0wOwogICAgY2luPj5DOwogICAgaWYoQz49MSAmJiBDPD0xMDApCiAgICB7CiAgICAgICAgd2hpbGUoQy0tKQogICAgICAgIHsKICAgICAgICAgICAgY2luPj5OOwogICAgICAgICAgICBpZihOLnNpemUoKTw9MjAwKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBzdHJpbmcgd3luaWs9bWF0aChOKTsKICAgICAgICAgICAgICAgIGNvdXQ8PHd5bmlrPDxlbmRsOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAKICAgIH0KCgp9