Tricknology

Interview

Time limit1sMemory limit1024 MB

Summary

For each query L R, count pairs x < y within [L, R] where the sum of all integers from x to y is prime.

Problem

Write a program that performs the following query.

$L\ R$ : For integers $x$ and $y$ that satisfy $L \leq x < y \leq R$ , output the number of integer pairs $(x, \:y)$ for which the sum of all natural numbers $k$ with $x \leq k \leq y$ is a prime number.

The first line contains the number of queries $Q$ . $(1 \leq Q \leq 500\ 000)$

Each of the next $Q$ lines contains one query, given as two positive integers $L$ and $R$ . $(2 \leq L < R \leq 500\ 000)$

For each query, print the answer on its own line.