Lonely Numbers

题意翻译

### 题目大意 我们规定对于两个不同的数字 $a,b$ ,如果$\gcd(a,b),\frac{a}{\gcd(a,b)},\frac{b}{\gcd(a,b)}$ 可以构成一个三角形,那么 $a,b$ 便是一组好朋友. 我们进一步规定,如果在一个集合中中,有一数字 $k$ 和这个集合中任意一个数字都不是朋友,那么数字 $k$ 就是一个孤独数字. 给定一个包含所有 $1$ 到 $n$ 整数的集合,求在该集合中有多少数字是孤独数字. ### 输入输出格式 第一行输入一个整数 $T$ 表示有 $T$ 组数据. 接下来一行 $T$ 个数字,其中第 $i$ 个数字为 $n_{i}$ ,表示你应解决当 $n=n_{i}$ 时的问题. 你应输出 $T$ 行,第 $i$ 行为当 $n=n_{i}$ 时孤独数字的数量. ### 样例解释 当 $n=1$ 时, $1$ 是集合中唯一的数字,因此它是孤独数字. 当 $n=5$ 时, 孤独数字为$1,3,5$. 当 $n=10$ 时, 孤独数字为$1,5,7$.

题目描述

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?

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

3
1 5 10

输出样例 #1

1
3
3

说明

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.