题目描述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

出题Author

FUDAN

来源Source