CF1423K.Lonely Numbers

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 \gt c$, $b + c \gt a$ and $c + a \gt 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?

在数字世界中，两个不同的数字是朋友，当且仅当它们既有大量共同点，又各自拥有独特的优点。

更准确地说，两个不同的数字 $a$ 和 $b$ 是朋友，当且仅当 $gcd(a,b)$、$\frac{a}{gcd(a,b)}$、$\frac{b}{gcd(a,b)}$ 可以构成一个三角形的三条边。

三个数 $a$、$b$ 和 $c$ 能构成三角形的三条边，当且仅当满足 $a + b \gt c$、$b + c \gt a$ 以及 $c + a \gt b$。

在一个数字集合中，若某个数字在该集合中没有任何朋友，则称其为“孤独的”。

给定一个包含所有从 $1, 2, 3, \dots, n$ 的数字的集合，问该集合中有多少个数字是孤独的？

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$.

第一行包含一个整数 $t$（$1 \leq t \leq 10^6$），表示测试用例的数量。

下一行包含 $t$ 个数字 $n_i$（$1 \leq n_i \leq 10^6$），表示在第 $i$ 个测试用例中，你需要对数字 $1, 2, 3, \dots, n_i$ 进行求解。

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

对于每个测试用例，在单独的行上输出答案：第 $1, 2, 3, ..., n_i$ 组中孤独数的个数。

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.

对于第一个测试用例，$1$ 是唯一的一个数，因此它是孤独的。

对于第二个测试用例（$n=5$），数字 $1$、$3$ 和 $5$ 是孤独的。

对于第三个测试用例（$n=10$），数字 $1$、$5$ 和 $7$ 是孤独的。