#include<bits/stdc++.h>
using namespace std;
const int a=1e6+5;
bool isprime[a+1];
void sieve()
{
    bool isprime[a+1];
    for(int i=0;i<=a;i++) isprime[i]=true;
    isprime[0]=false;
    isprime[1]=false;
    for(int i=2;i*i<=a;i++)
    {
        if(isprime[i]=true)
        {
            for(int j=i*i;j<=a;j+=i)
                isprime[i]=false;
        }
    }
}
std;

int main()
{
    freopen("beaunum.  freopen("cloprime.inp","r",stdin);
    freopen("beaunum.freopen("cloprime.out","w",stdout);
    bool check[1000000];
  for (int i=2;i<=1000000;i++){
    check[i]=true;
  }
  check[0]=false;
  check[1]=false;
  for (int i=2;i<=1000000;i++){
    if (check[i]==true){
      for (int j=2*i;j<=1000000;j+=i){
        check[j]=false;
      }
    }
  }
  long long n,m,d=0;
    cin>>n;
    m=(int)pow(n,1/4.);
    sieve();
    for (int i=2;i<=m;i++)
        if(isprime[i]=true) d++;
    cout<<d;


n;cin>>n;
  long long x;
  for(int i=1;i<=n;i++){
     cin>>x;
     while(check[x]==false) x--;
     cout<<x<<endl;
  }
}