1253 : A Simple MST Problem

Description

For the positive integer \(x\), we define the number of its different prime factors as \(\omega(x)\). For example, \(\omega(1)=0,\omega(8)=1,\omega(12)=2\).

In this problem, we treat each positive integer as a node. When we build an edge between node \(x\) and node \(y\), we will cost \(\omega(lcm(x,y))\), where \(lcm(x,y)\) represents the least common multiple of \(x\) and \(y\).

Next, you will be given \(T\) queries. For the \(i\)-th query we will give two integers \(l_i,r_i\). What you need to answer is, when only considering nodes \(l_i,l_i+1,\cdots r_i\), what is the minimum cost if we build edges so that these \(r_i-l_i+1\) nodes can reach each other.

Note that all of the queries are distinct and in \(i\)-th query you can only build an edge between \(x,y\) when \(l_i\le x,y\le r_i\).

Input

The first line contains an integer \(T(T\le 50000)\) , indicating the number of queries.

For the next \(T\) lines, the \(i\)-th line contains two integers \(l_i,r_i(1\le l_i\le r_i\le 10^6)\), indicating a query.

It is guaranteed that \(\sum_{i=1}^T r_i \le 10^6\).

Output

For each query, output an integer as your answer.

Sample

5
1 1
4 5
1 4
1 9
19 810
##CASE##
2
27 30
183704 252609

0
2
3
9
1812
##CASE##
8
223092

Hint

Source

Author

FUDAN