Prime Counters

Problem Statement

Given a number N, let CP(N) denotes the number of prime numbers between 1 and N (inclusive of N).

We call N a prime counter if CP(N) is a prime (N need not to be a prime).

For example: CP(3) = 2, CP(4) = 2, CP(5) = 3, CP(7) = 4

Input Format

An integer T, number of test cases each containing two positive integers L and R separated by space.

Output Format

T lines containing the number of prime counters between L and R (both inclusive) for each ith test case.

Constraints

1 <= T <= 10^6

1 <= L, R <= 10^7