Untitled

※ The act of posting and sharing problems & solutions to the outside of the company online/offline is strictly prohibited.

Problems of the SW Expert Academy are only open to Samsung Electronics employees.

 

Restrictions     Execution time : 1 sec(C/C++) / 2 sec(JAVA)

Memory : Maximum 256MB available for heap and stack combined (note: Maximum 1 MB can be used for stack)

submit limit     99 times

Score   When you submit your code, you can see immediate result from server.

Pass : You have successfully passed the qualification test.

Fail : you got 0 score or partial score because of wrong answer, runtime error, time out so on

evaluation. Final result can be different from the result during the test because another input will be used for actual evaluation.

====

 

Count the number of prime numbers from 2 to N.

 

[Input]

 

The first line contains a number of test cases known as T.

 

Each test case has 1 integer number N. (2 <= N <= 2,000,000).

 

[Output]

 

For each test case, print ‘#x’(test case number) and the count of prime numbers from 2 to N.

 

Input Example

 

2

2

5

// T : Number of test cases

 

Output Example

 

#1 1

#2 3