题目背景

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

题目描述

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$ 行，每行一个整数，代表答案。

2
1 2
114514 1919810

1
1047

提示

样例解释

对于第一组数据，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$。

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