Buddy is known for his love for primes. He claims that if given a number he can instantly tell wether it is a prime or not. Golu challneges his this claim and gives Buddy $2$ numbers $X$ and $Y$, $Q$ times and asks him to tell the number of primes between $X$ and $Y$($X$ and $Y$ included). Buddy lately has been quite rusty with his knowledge of primes as he is out of practice and hence asks for your help so that he can prove his claim right. Help him to tell count of primes from  $X$ to $Y$.

Constraints:

1 ≤ $Q$ ≤ 10⁵
1 ≤ $X$ ≤ $Y$≤ 10⁷
0 ≤ $Y-X$ ≤ 10³

Input:
First line of the input contains the number $Q$, Each of the next $Q$ lines contain $2$ numbers $X$ and $Y$.

Output:

For each given $X$ and $Y$, print the count of number which are prime between $X$ and $Y$ ($X$ and $Y$ included) in a new line.