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$$$.
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$$$.
For each query, output an integer as your answer.
5 1 1 4 5 1 4 1 9 19 810
0 2 3 9 1812
2 27 30 183704 252609
8 223092
