Lonely Numbers

1000ms

262144K

Description:

In number world, two different numbers are friends if they have a lot in common, but also each one has unique perks.

More precisely, two different numbers $$$a$$$ and $$$b$$$ are friends if $$$gcd(a,b)$$$, $$$\frac{a}{gcd(a,b)}$$$, $$$\frac{b}{gcd(a,b)}$$$ can form sides of a triangle.

Three numbers $$$a$$$, $$$b$$$ and $$$c$$$ can form sides of a triangle if $$$a + b > c$$$, $$$b + c > a$$$ and $$$c + a > b$$$.

In a group of numbers, a number is lonely if it doesn't have any friends in that group.

Given a group of numbers containing all numbers from $$$1, 2, 3, ..., n$$$, how many numbers in that group are lonely?

Input:

The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^6)$$$ - number of test cases.

On next line there are $$$t$$$ numbers, $$$n_i$$$ $$$(1 \leq n_i \leq 10^6)$$$ - meaning that in case $$$i$$$ you should solve for numbers $$$1, 2, 3, ..., n_i$$$.

Output:

For each test case, print the answer on separate lines: number of lonely numbers in group $$$1, 2, 3, ..., n_i$$$.

Sample Input:

3
1 5 10

Sample Output:

1
3
3

Note:

For first test case, $$$1$$$ is the only number and therefore lonely.

For second test case where $$$n=5$$$, numbers $$$1$$$, $$$3$$$ and $$$5$$$ are lonely.

For third test case where $$$n=10$$$, numbers $$$1$$$, $$$5$$$ and $$$7$$$ are lonely.

Informação

Provedor Codeforces

Código CF1423K