T710344 [CFCOI-R4-T1] 数论分块
题目背景
$\text{calc.cpp},1 \text{ s},512 \text{ MiB}$
题目描述
规定：
$$f(x)=\sum_{i=1}^{x} \biggl\lfloor \dfrac{x}{i} \biggr\rfloor$$
$q$ 次询问，每次给定 $n$，需求出
$$g(n)=\sum_{i=1}^{n} \Big( f(i) \bmod 2 \Big)$$
的值。
输入格式
第一行，一个整数 $q$。
接下来 $q$ 行，第 $i$ 行为整数 $n_i$，表示求 $g(n_i)$ 的值。
输出格式
输出 $q$ 行，第 $i$ 行输出 $g(n_i)$。
说明/提示
#### 大样例
这里原本有一个 $q=100$ 的样例，被 Hamburger999 删去了。
#### 数据范围
对于 $100\%$ 的数据：$1 \le n \le 10^{18}$。
除样例外，$q=5 \times 10^5$。