#include <iostream>
#include <fstream>
using namespace std;
long long euclid(long long a, long long b)
{
    long long c;
    while (b)
    {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}
long long desc(long long n)
{
    long long d,e,l,m;
    m=n;
    l=-1;
    d=2;
    e=0;
    while(n%d==0)
    {
        n=n/d;
        e++;
    }
    if(e>0)
    {
        //cout<<d<<" "<<e<<endl;
        l=e;if(l==1)return 0;
    }
    d=3;
    while(n>1)
    {
        e=0;
        while(n%d==0)
        {
            n=n/d;
            e++;
        }
        if(e>0)
        {
            //cout<<d<<" "<<e<<endl;
            if(l==-1)l=e;
            else l=euclid(l,e);
            if(l<=1)return 0;
        }
        if(d*d>=n)d=n;
        else d=d+2;
    }
    if(l<=1)return 0;
    return m;
}
long long jos(long long n,long long v)
{
    long long m=n,p1,p2;

    n++;
    do
    {
        n--;
        p1=desc(n);
        //cout<<n<<" "<<p1<<endl;
    }
    while(p1==0&&n>2);
    //cout<<p1<<" ";
    n=m;n--;
    do
    {
        n++;if(n-m>n-p1&&p1>0)return p1;
        p2=desc(n);
        //cout<<n<<" "<<p2<<endl;
    }
    while(p2==0&&n<v);
    //cout<<p2<<endl;
    if(p1==0)return p2;
    if(p2==0)return p1;
    if(m-p1<=p2-m)return p1;
    else return p2;
}
int main()
{
    ifstream f("abx.in"); ofstream g("abx.out");
    long long n,m,x,i;
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        f>>x;
        g<<jos(x,m)<<endl;

    }
    f.close();
    g.close();
    //cout<<desc(100);
    //cout<<euclid(2,2);
    return 0;
}