P14640 【OIMO Round 1】校验

**请注意本题特殊的时间限制，并使用更快的读写方式。**

X 有一些数，她对数有不同的喜爱程度。具体的，她对某个数的喜爱度计算方法如下： 定义一个正整数 $x$ 的校验值为 $(-1)^{\Omega(x)}$，其中 $\Omega(x)$ 为 $x$ 的**可重**素因子个数。比如，$12$ 的校验值为 $(-1)^3=-1$，因为它有 $3$ 个素因子 $2,2,3$。 X 对一个数的喜爱度是这个数的**所有因数**的校验值之和。例如，X 对 $2$ 的喜爱度为 $0$，因为 $1$ 的校验值为 $1$，$2$ 的校验值为 $-1$。 H 有一个区间 $[l,r]$，他想知道 X 对这个区间内所有数的喜爱度之和。 **形式化题意**：给定 $l,r$，求 $\sum\limits_{i=l}^r\sum\limits_{x\mid i}(-1)^{\Omega(x)}$ 的值，其中 $\Omega(x)$ 为 $x$ 的**可重**素因子个数。

第一行一个正整数 $T$，表示测试数据组数。 接下来 $T$ 行，每行两个正整数 $l,r$，表示一个区间。

输出 $T$ 行，每行一个整数，代表答案。

#### 样例解释 对于第一组数据，X 对 $1$ 的喜爱度为 $1$，对 $2$ 的喜爱度为 $0$，因此和为 $1$。 **本题采用捆绑测试**。 - Subtask 1（10 points）：$T\le 10$，$1\le l\le r\le 100$； - Subtask 2（25 points）：$1\le l\le r\le 10^5$； - Subtask 3（65 points）：无特殊限制。 对于所有测试数据，$1\le T\le 10^6$，$1\le l\le r\le 10^9$。 **请注意本题特殊的时间限制，并使用更快的读写方式。**