这是一个交互式问题。

对于两个正整数 $x, y$，我们定义 $\pi(x, y)$ 为同时整除 $x$ 和 $y$ 的不同质数的个数。例如 $\pi(2, 3) = 0$，$\pi(8, 16) = 1$ 以及 $\pi(30, 105) = 2$。

对于两个正整数 $a, b$，其中 $a \le b$，我们定义 $S(a, b)$ 为满足 $a \le x < y \le b$ 的所有整数对 $(x, y)$ 的 $\pi(x, y)$ 之和。

你的任务是计算多个查询对 $(a, b)$ 的 $S(a, b)$ 值。为了增加挑战性，所有查询必须在线回答。

输入格式

输入的第一行包含一个整数 $q$ ($1 \le q \le 5 \cdot 10^4$)，表示查询的数量。接下来的 $q$ 行描述了这些查询。第 $i$ 行包含两个整数 $a_i, b_i$ ($1 \le a_i \le b_i \le 10^6$)。

注意，第 $i$ 个查询 ($i \ge 2$) 只有在你输出了第 $(i-1)$ 个查询的答案后才会出现在输入中。

输出格式

你应该打印恰好 $q$ 行。第 $i$ 行应包含值 $S(a_i, b_i)$。

在回答每个查询后，请务必刷新输出。

样例

输入 1

4
1 5
6 6
3 9
1 500000

输出 1

1
0
6
56529651093