V. *【线性筛：欧拉函数】法雷级数

传统题

1000ms

512MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题意】

法雷级数 $F_i$ 的定义如下：给定一个 $i \ (i \ge 2)$ ，那么所有的 $a/b \ （0 < a < b \le i$ 且 $gcd(a,b)==1 ）$ 组成了 $F_i$ ，例如：

$F_2 = {1/2}$

$F_3 = {1/3, 1/2, 2/3}$

$F_4 = {1/4, 1/3, 1/2, 2/3, 3/4}$

$F_5 = {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5}$

你的任务就是统计对于给出的i，Fi集合的元素个数。

第一行 $n \ (1 \le n \le 10000)$ 。

下来 $n$ 行，每行一个整数 $x \ (2 \le x \le 2000 0000)$ ，表示求 $F_x$ 的元素个数。

每次询问输出一行一个整数，即 $F_x$ 的元素个数。