线性筛+二分,特判1
#include <bits/stdc++.h>
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define lowbit(x) (x&-x)
using namespace std;
const int N = 1E5+10,PN = N/2;
vector<int> prime;
int nprime[N];
void Euler()
{
for(int i=2;i<=N;i++)
{
if(!nprime[i])
nprime[i]=i,prime.push_back(i);
rep(j,0,prime.size())
{
if(prime[j]*i>N||prime[j]>nprime[i])
break;
else
nprime[i*prime[j]]=prime[j];
}
}
}
int ask(int x)
{
int pos=upper_bound(prime.begin(),prime.end(),x)-prime.begin();
return prime[pos]-prime[pos-1]-1;
}
int main()
{
Euler();
int t,x;
cin>>t;
repd(i,1,t)
{
cin>>x;
if(x==1||nprime[x]==x) cout<<0<<endl;
else cout<<ask(x)<<endl;
}
return 0;
}