Answer the following \(Q\) queries:

Count the number of prime numbers in the range \([A, B]\).

Input Specification

The first line of the input will contain an integer \(Q\) \((1 \le Q \le 10^6)\), indicating the number of queries.

The next \(Q\) lines will each contain two integers \(A_i\) and \(B_i\), where \(1 \le A_i \le B_i \le 10^8\).

Output Specification

Output \(Q\) lines, where the \(i\)-th line represents the number of prime numbers in the range \([A_i, B_i]\).

Subtask 1 [20%]

\(1 \le A_i \le B_i \le 10^2\)

Subtask 2 [30%]

\(1 \le A_i \le B_i \le 10^3\)

Subtask 3 [50%]

No additional constraints.

Sample Input

2
2 17
1 4

Sample Output

7
2

Sample Explanation

The \(7\) prime numbers in the given range are \(2\), \(3\), \(5\), \(7\), \(11\), \(13\), and \(17\).

The \(2\) prime numbers in the range \([1, 4]\) are \(2\) and \(3\).