对于正整数 $x$，我们定义其不同质因子的个数为 $\omega(x)$。例如，$\omega(1) = 0, \omega(8) = 1, \omega(12) = 2$。

在本题中，我们将每个正整数视为一个节点。当我们建立节点 $x$ 和节点 $y$ 之间的边时，代价为 $\omega(\text{lcm}(x, y))$，其中 $\text{lcm}(x, y)$ 表示 $x$ 和 $y$ 的最小公倍数。

接下来，你将收到 $T$ 次询问。对于第 $i$ 次询问，给定两个整数 $l_i, r_i$。你需要回答：仅考虑节点 $l_i, l_i + 1, \dots, r_i$ 时，若要使这 $r_i - l_i + 1$ 个节点相互连通，所需的最小代价是多少。

注意，所有的询问都是独立的，且在第 $i$ 次询问中，你只能在满足 $l_i \le x, y \le r_i$ 的节点 $x, y$ 之间建立边。

输入格式

第一行包含一个整数 $T(T \le 50000)$，表示询问次数。 接下来的 $T$ 行，第 $i$ 行包含两个整数 $l_i, r_i(1 \le l_i \le r_i \le 10^6)$，表示一次询问。 保证 $\sum_{i=1}^T r_i \le 10^6$。

输出格式

对于每次询问，输出一个整数作为答案。

样例

样例输入 1

5
1 1
4 5
1 4
1 9
19 810

样例输出 1

0
2
3
9
1812

样例输入 2

2
27 30
183704 252609

样例输出 2

8
223092