트릭놀로지

면접 대비

시간 제한1초메모리 제한1024 MB

요약

각 질의 L, R에 대해 L 이상 R 이하의 정수 쌍 (x, y) 가운데 x부터 y까지 연속된 자연수의 합이 소수인 쌍의 개수를 구합니다.

문제

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

$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)$

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