Với hai số nguyên dương ~A, B~ cho trước ~(A ≤ B)~. Đếm số lượng các số nguyên tố thuộc đoạn ~[A,B]~.

Input: Dòng đầu tiên ghi số ~k~ (1 ≤ k ≤ ~10^3~) là số các đoạn ~[A,B]~; ~k~ dòng tiếp theo, mỗi dòng ghi 2 số ~A, B~. (1 ≤ ~A ≤ B~ ≤ ~10^7~)

Output: gồm ~k~ dòng, dòng thứ ~i~ ghi một số là số các số nguyên tố trong đoạn ~[A, B]~ thứ ~i~ đã cho.

Ví dụ:

INPUT

3
2 20
20 100
1 100

OUTPUT

8
17
25