【题目背景】

（Rainbow和Freda正在城堡里玩得开心的时候，外面传来一阵声音：小猫乖乖，把门开开~）
Rainbow：不好！是汪星人入侵！
Freda：肿么办肿么办T_T？
Rainbow：我们先躲起来观察一下汪星人的动态吧>_<！

【题目描述】

Rainbow和Freda躲到了瞭望塔里，发现汪星人这次的目标有些奇怪。
Rainbow的城堡有N扇门，从1到N标号，它们初始时都是关着的。现在来了N只汪星人，第i只汪星人会把所有标号能被i整除的门的状态改变（即把标号能被i整除的关着的门打开，把标号能被i整除的开着的门关上）。
Rainbow为城堡定义了一个不安全指数——即最后打开着的门的数目。Rainbow想请你帮忙计算，城堡的不安全指数是多少？

【输入格式】

每个测试点包括多组测试数据。
第一行一个整数T，表示一共有T组测试数据。
接下来T行每行一个整数N，表示Rainbow城堡的门的数量。

【输出格式】

输出T行，第i行的数字表示，对于第i个N，城堡的不安全指数。

【样例输入】

4 
 4 
 10 
 16 
 27 
 

【样例输出】

2 
 3 
 4 
 5 
 

【提示】

样例解释:　　　
当N=4的时候，4扇门情况如下（1表示开，0表示关）：
没有汪星人来的时候：0000
第一只汪星人来后：1111
第二只汪星人来后：1010
第三只汪星人来后：1000
第四只汪星人来后：1001
所以答案为2
对于20%的数据，T<=100.
对于100%的数据，T<=20000，N<=50000. 

解题报告：

本题我看到后没什么思路，果断模拟。不过，模拟也需要一个技巧，那就是，第i个人一定只能开关i以后的门。这样，我们就可以开一个记录门开关的数组，将50000个人开关门以后各个门的开关情况记录下来。这样开一个ans数组记录答案。。

代码：

C++语言: 

made by PaulInsider!
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int q[50005]={0};
bool used[50005]={0};
int n,m;
int main()
{
   freopen ("wang.in","r",stdin);
   freopen ("wang.out","w",stdout);
   for (int i=2;i<=50000;i++)
   {
       for (int j=i;j<=50000;j+=i)
       {
           used[j]=!used[j];
       }
   }
   for (int i=1;i<=50000;i++)
   {
       q[i]=q[i-1]+(!used[i]);
   }
   cin>>n;
   for (int i=0;i<n;i++)
   {
       cin>>m;
       cout<<q[m]<<endl;
   }
   return 0;
}