ALICESIE - Alice Sieve

Alice最近学习了埃拉托色尼筛选法，一个用于在任何给定范围内寻找素数的筛选算法。如同我们期望的那样，她被这个算法简洁优雅的气质深深地震惊了。 现在，Alice决定要自己设计一个算法模型，Alice筛法，正式定义其方法如下 1）确定要在n以内的数的限制中使用ALICE筛法（给出范围），创建一个包含了从n到2的所有整数的严格下降序列 2）在开始的时候，令p=n 3）在序列中标记p的所有真因数（不包括p，即不含n） 4）找到p-1到2中所有数中最大的还没有被标记的数q，令p=q 5）若q不存在，停止，否则从第3步开始继续重复。 Alice想要知道，对于每一个给定的N，筛法结束后序列中还有多少没有被标记的数。 输入格式：第一行是一个整数T，表示有T组数据。后面每一行都有一个给定的N。 输出：T行。每行是对于每一个N，没有被标记的数的数量。 感谢@Carolina 提供的翻译

Alice has recently learned to use the Sieve of Eratosthenes, an ancient algorithm for finding all prime numbers up to any given limit. As expected, she was really impressed by it's simplicity and elegancy. Now, she has decided to design her own sieve method: The Sieve of Alice, formally defined by the following procedure, which determines the Sieve of Alice up to a given limit N. 1. Create a list of consecutive integers from N to 2 (N, N-1, N-2, ..., 3, 2). All of those N-1numbers are initially unmarked. 2. Initially, let P equal N, and leave this number unmarked. 3. Mark all the proper divisors of P (i.e. P remains unmarked). 4. Find the largest unmarked number from 2 to P – 1, and now let P equal this number. 5. If there were no more unmarked numbers in the list, stop. Otherwise, repeat from step 3. Unfortunately, Alice has not found an useful application for it's Sieve. But she still wants to know, for a given limit N, how many integers will remain unmarked.

The first line contains an integer T, the number of test cases (1

Output T lines, one for each test case, containing the required answer.

3
2
3
5

1
2
3