Unfortunately for Max, Mr. Gugoiu has caught him playing games during class! Somehow, Annie did not get caught—quite unfair, if you ask me.

As a result, Mr. Gugoiu has given Max a proposition. If Max can solve his challenge (which he got from Ms. Gugoiu), Max will be spared. If he cannot, he will be given an extra physics assignment to complete. The challenge is as follows:

• Given two positive integers, ~N~ and ~M~,
• You must find the number of positive integer pairs, ~(A, B)~, such that ~A > B~ and ~N \le A+B \le M~.
• For each pair, you must then construct two right triangles: one with shorter sides ~A~ and ~N~, the other with shorter sides ~B~ and ~N~.
• The difference between the squares of the longest side of each triangle must be a prime number.

He gives Max two integers ~N~ and ~M~ (the sample input), but Max quickly solves it. Slightly impressed, Mr. Gugoiu decides to give Max ~T~ such cases. Can you help Max solve them all? Specifically, for every case, find the number of pairs ~(A, B)~ that satisfy the conditions.

Constraints

~1 \le T \le 10^5~

Subtask 1 [50%]

~1 \le N_i \le M_i \le 50~

Subtask 2 [50%]

~1 \le N_i \le M_i \le 10^6~

Input Specification

The first line of input will contain the integer ~T~.

The next ~T~ lines each contain two integers, ~N_i~ and ~M_i~.

Output Specification

Output ~T~ lines, the ~i~-th line containing the answer to the ~i~-th case.

Sample Input

1
10 15

Sample Output

2

Sample Explanation

The two cases are ~(6, 5)~ and ~(7, 6)~.

The two triangles created with ~(6, 5)~ have side lengths ~(6, 10, \sqrt{136})~, and ~(5, 10, \sqrt{125})~. Taking the difference of the squares of the longest sides yields ~136-125=11~, which is a prime number.

The two triangles created with ~(7, 6)~ have side lengths ~(7, 10, \sqrt{149})~, and ~(6, 10, \sqrt{136})~. Taking the difference of the squares of the longest sides yields ~149-136=13~, which is a prime number.