호기심

남규는 호기심이 많다. 남규는 두 정수 $a$와 $b$를 받아 그 사이에 있는 소수로 값을 계산하는 함수 $F$를 만들었다.

닫힌 구간 $[a, b]$에 들어가는 소수를 작은 것부터 차례대로 $A_1 < A_2 < \dots < A_n$이라고 하자. $F(a, b)$는 홀수 번째 소수에 3을 곱해서 더하고, 짝수 번째 소수는 그대로 빼서 얻는 값이다.

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

마지막 항의 부호는 소수의 개수 $n$이 정한다. $n$이 홀수이면 $+3A_n$으로 끝나고, $n$이 짝수이면 $-A_n$으로 끝난다.

예를 들어 $F(3, 7)$을 보자. 3 이상 7 이하의 소수는 3, 5, 7 세 개이므로 값은 $3 \times 3 - 5 + 3 \times 7 = 25$이다.

구간에 소수가 하나도 없으면 $F(a, b)$는 0이다.

첫 줄에 질문의 개수 $q$가 주어진다. ($1 \le q \le 10^5$)

다음 $q$개의 줄에 질문이 한 줄에 하나씩 주어진다. 각 줄에는 두 정수 $a$와 $b$가 공백으로 구분되어 있다. ($1 \le a \le b \le 10^5$)

각 질문에 대해 $F(a, b)$의 값을 입력에 주어진 순서대로 한 줄에 하나씩 출력한다.