시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
8 초 256 MB 13 4 2 18.182%

문제

This is an interactive problem.

For two positive integers $x,y$, we define $\pi(x,y)$ to be the number of distinct primes that divide both $x$ and $y$. For example $\pi(2,3)=0$, $\pi(8,16)=1$ and $\pi(30,105)=2$.

For two positive integers $a,b$, where $a\leq b$, we define $S(a,b)$ to be the sum of values $\pi(x,y)$ over all pairs of integers $(x,y)$ satisfying $a\leq x < y\leq b$.

Your task is to compute the values $S(a,b)$ for many query pairs $(a,b)$. To make your task more challenging, all the queries have to be answered online.

입력

The first line of the input contains a single integer $q$ ($1\leq q\leq 5\cdot 10^4$), denoting the number of queries. The next $q$ lines describe the queries. The $i$-th of these lines contains two integers $a_i,b_i$ ($1\leq a_i\leq b_i\leq 10^6$).

Note that the $i$-the query ($i\geq 2$) will be available at the input only after you output the answer to the $(i-1)$-th query.

출력

You should print exactly $q$ lines. The $i$-th of these lines should contain the value $S(a_i,b_i)$.

Do not forget to flush the output after answering each query.

예제 입력 1

4
1 5
6 6
3 9
1 500000

예제 출력 1

1
0
6
56529651093

채점

  • 예제는 채점하지 않는다.