Vì biết Harry rất kém về số nguyên tố nên trong kì thi này của trường Hogwarts, giáo sư Snape đã ra một bài toán hóc búa như sau:

“Cho 2 số nguyên dương ~a, b~. Hãy tìm số lượng các số trong khoảng ~[a, b]~ sao cho số lượng ước của chúng là một số nguyên tố”.

Không chỉ dừng lại đó, giáo sư Snape còn đánh đố Harry bằng cách không chỉ cho một bộ ~a, b~ mà cho những ~T~ bộ số.

Harry rất cần qua kì thi này nên anh ấy nhờ đến các bạn lập trình chương trình để giải bài toán của thầy Snape.

Yêu cầu: Cho ~T~ bộ số ~(a, b)~, với mỗi bộ hãy tìm số lượng các số trong khoảng ~[a, b]~ có số lượng ước là một số nguyên tố.

Input

• Dòng đầu chứa số nguyên dương ~T~ là số bộ test.
• ~T~ dòng sau mỗi dòng gồm 2 số nguyên dương ~a, b~.

Output

• ~T~ dòng, dòng thứ ~i~ là kết quả của bộ test thứ ~i~.

Sample Input 1

5
12 400
412 1000
32 100
1910 3000
1 100

Sample Output 1

82
93
17
141
32