学步园

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=10010;

struct node{
	int no,val;
	node() {}
	node(int a, int b): no(a), val(b) {}
}v[N];

int eu[N],n;
void eular()
{
	int i,j;
	for(i=2;i<N;i++)
		if(!eu[i])
	for(j=i;j<N;j+=i){
		if(!eu[j]) eu[j]=j;
		eu[j]=eu[j]/i*(i-1);
	}
}

int Query(int x)
{
	int l,r,mid;
	l=0, r=n-1;
	while(r-l>1)
	{
		mid=(l+r)/2;
		if(v[mid].val>x)
			r=mid;
		else
			l=mid;
	}
	if(v[l].val<x && v[r].val>=x)
		return v[r].no;
	return v[l].no;
}

int main()
{
    // freopen("in","r",stdin);
    // freopen("out","w",stdout);
    int i,j,t,m,tmp;
    memset(eu,0,sizeof(eu));
    eular();
    for(i=1;i<N;i++)
    	v[i]=node(i,eu[i]);
    tmp=v[1].val;
    for(i=2,j=0; i<N;i++)
    {
    	if(v[i].val>tmp) v[j++]=v[i];
    	tmp=max(tmp,v[i].val);
    }
    n=j;
    
    scanf("%d",&t);
    while(t--)
    {
    	scanf("%d",&m);
    	printf("%d\n",Query(m));
    }
    return 0;
}