28427번 - Tricknology

다음 쿼리를 수행하는 프로그램을 작성하시오.

• $L\ R$: $L \leq x < y \leq R$을 만족하는 정수 $x$, $y$에 대하여, $x \leq k \leq y$를 만족하는 모든 자연수 $k$의 합이 소수가 되게 하는 모든 정수 쌍 $(x, \:y)$의 개수를 출력한다.

첫째 줄에 쿼리의 개수 $Q$가 주어진다. $(1 \leq Q \leq 500\ 000)$

다음 $Q$개의 줄에는 각각의 쿼리를 나타내는 양의 정수 $L$, $R$이 주어진다. $(2 \leq L < R \leq 500 \ 000)$

각각의 쿼리마다 한 줄에 하나씩 정답을 출력한다.