남규는 호기심이 많다. 호기심이 많은 남규는 a와 b 사이의 소수들의 합과 차를 이용한 특수한 함수 F를 만들었다. 남규는 이 특수한 함수의 결과값을 알고 싶다.</p>

함수 F(a,b)는 a와 b 사이의 소수를 순서대로 다음과 같은 규칙에 따라 계산하고, 그 값을 반환한다.

3×A₁ - A₂ + 3×A₃ - A₄ + 3×A₅ - A₆ ..... A_n (a ≤ A₁ < … < A_n ≤ b , A_i는 소수이다.)

질문이 F(3, 7) 이라면 3과 7 사이에는 3, 5, 7 총 3개의 소수가 있고, 규칙에 따라 계산한 결과는

3×3 - 5 + 3×7 = 25 이다.

입력 형식

첫 줄에는 질문의 개수 n이 주어진다. 다음 줄 부터 차례대로 함수의 입력 a, b가 주어진다. (1 ≤ a ≤ b ≤ 10⁵) 또한 남규는 호기심이 많기 때문에 매우 많은 질문을 한다. 따라서 질문의 수 n은 최대 10⁵ 개이다.

출력 형식

남규가 물어본 질문 a, b에 대한 답변 F(a, b)을 각 줄에 하나씩 순서대로 출력한다.

예제 입력

2
3 7
5 7

예제 출력

25
8