소수

이 문제는 인터랙티브 문제이다.

양의 정수 $x,y$에 대해, $\pi(x,y)$를 $x$와 $y$를 모두 나누는 서로 다른 소수의 개수로 정의한다. 예를 들어 $\pi(2,3)=0$, $\pi(8,16)=1$, $\pi(30,105)=2$이다.

양의 정수 $a,b$ ($a\leq b$)에 대해, $S(a,b)$를 $a\leq x < y\leq b$를 만족하는 모든 정수 쌍 $(x,y)$에 대한 $\pi(x,y)$ 값의 합으로 정의한다.

여러 질의 쌍 $(a,b)$에 대해 $S(a,b)$를 계산해야 한다. 모든 질의는 온라인으로 답해야 한다.

첫째 줄에 질의의 개수 $q$가 주어진다 ($1\leq q\leq 5\cdot 10^4$). 다음 $q$개의 줄에 질의가 주어진다. $i$번째 줄에는 두 정수 $a\_i,b\_i$가 주어진다 ($1\leq a\_i\leq b\_i\leq 10^6$).

$i$번째 질의 ($i\geq 2$)는 $(i-1)$번째 질의에 대한 답을 출력한 뒤에야 입력에서 확인할 수 있다.

정확히 $q$개의 줄을 출력한다. $i$번째 줄에는 $S(a\_i,b\_i)$ 값을 출력한다.

각 질의에 답한 뒤 출력 버퍼를 비워야 한다.