ALICESIE - Alice Sieve

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.

Input

The first line contains an integer T, the number of test cases (1 ≤ T ≤ 104) . Each of the next T lines contains an integer N (2 ≤ N ≤ 106).

Output

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

Example

Input:
3
2
3
5

Output:
1
2
3

Added by:Paulo Costa
Date:2012-02-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC ASM64 MAWK BC BF C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY3 R RACKET RUST SCM qobi CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:UNI

hide comments
2014-12-24 22:14:46 Christopher Almquist
Python 2.7 worked fine for me.
2014-12-15 07:27:05 Andrew Stephenson
Just a note to anyone having trouble with this one, try writing in non-interpreted languages. I tried it at first in python 3.4, and the server seemed to have issues with python. So then I tried java and it was over the time limit (even though the algorithm was reasonable). The EXACT same code, ported line for line from java to c++, easily passed.

Last edit: 2014-12-18 07:06:38
2014-12-07 20:53:38 Cameron Jones


Last edit: 2014-12-07 20:54:47
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.