Curiosity

Namgyu is a curious person. He built a function $F$ that takes two integers $a$ and $b$ and computes a value from the primes that lie between them.

Let the primes inside the closed interval $[a, b]$, listed from smallest to largest, be $A_1 < A_2 < \dots < A_n$. The function $F(a, b)$ multiplies every odd numbered prime by 3 and adds it, then subtracts every even numbered prime as it is.

$F(a, b) = 3A_1 - A_2 + 3A_3 - A_4 + 3A_5 - A_6 + \dots$

The count $n$ decides the sign of the last term. If $n$ is odd the sum ends with $+3A_n$, and if $n$ is even it ends with $-A_n$.

For example, consider $F(3, 7)$. The primes from 3 to 7 inclusive are 3, 5, and 7, so the value is $3 \times 3 - 5 + 3 \times 7 = 25$.

If the interval holds no prime at all, $F(a, b)$ is 0.

The first line contains the number of questions $q$. ($1 \le q \le 10^5$)

Each of the next $q$ lines holds one question as two integers $a$ and $b$ separated by a space. ($1 \le a \le b \le 10^5$)

For each question, print the value of $F(a, b)$ on its own line, in the order the questions are given.