Primes

This is an interactive problem.

For two positive integers $x,y$, define $\pi(x,y)$ as 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$ with $a\leq b$, define $S(a,b)$ as the sum of $\pi(x,y)$ over all pairs of integers $(x,y)$ satisfying $a\leq x < y\leq b$.

Your task is to compute $S(a,b)$ for many query pairs $(a,b)$. All queries must be answered online.

The first line contains a single integer $q$ ($1\leq q\leq 5\cdot 10^4$), 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$).

The $i$-th query ($i\geq 2$) is available in the input only after you output the answer to the $(i-1)$-th query.

Print exactly $q$ lines. The $i$-th line must contain the value $S(a\_i,b\_i)$.

Flush the output after answering each query.