CSG-CPC
Online Judge

# 1253 : A Simple MST Problem

Time Limit: 1 Sec     Memory Limit: 256 Mb     Submitted: 39     Solved: 14

## 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$$.

## 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

FUDAN