Trong căn phòng học Độc Dược, nằm trong tầng hầm lâu đài Huyền Bí, ánh đèn dầu mờ ảo làm không khí trở nên ngột ngạt và căng thẳng. Kỳ thi sát hạch sắp đến và mối lo lớn nhất của Hạnh Phúc không phải là kỳ thi chung, mà là bài kiểm tra đột xuất do Giáo sư Siêu Năng đề ra.

Giáo sư luôn dành cho Hạnh Phúc sự "quan tâm" đặc biệt, và lần này, ông quyết tâm đánh gục cậu bằng chủ đề mạnh mẽ: Các con số nguyên tố và tính chất Số học thuật (Arithmancy). Bảng đen ngập những công thức ma thuật cổ, Giáo sư cất giọng trầm lạnh, mỉa mai: "Hạnh Phúc! Ta e rằng cái danh tiếng 'Cậu bé sống sót' sẽ không thể giúp mi tính toán nổi những con số này. Để vượt qua buổi học hôm nay và không bị cấm túc cả tháng, mi phải giải quyết bài toán mê trận số nguyên tố của ta."

Giáo sư cho hai số nguyên dương ~a~ và ~b~, đại diện cho một khoảng năng lượng phép thuật ~[a, b]~. Nhiệm vụ của Hạnh Phúc là phải đếm xem trong khoảng đó có bao nhiêu số "Đặc Biệt". Một số được coi là "Đặc Biệt" nếu tổng số lượng ước số của nó là một số nguyên tố.

Giáo sư đã cài đặt thêm những quy tắc khắc nghiệt: Ông không chỉ đưa ra một cặp ~(a, b)~ duy nhất mà đưa ra tới ~T~ bộ số liên tiếp, bắt buộc Hạnh Phúc phải đưa ra đáp án cực kỳ nhanh chóng. Đặc biệt, ở thử thách tối cao (dành cho những Phù thủy xuất sắc), tầm biến thiên của ~a~ và ~b~ có thể lên tới ~10^{12}~! Ở mức năng lượng cực lớn này, Giáo sư siết chặt điều kiện: số lượng ước số của số "Đặc Biệt" không chỉ là số nguyên tố, mà phải là một số nguyên tố LỚN HƠN ~2~ (tức là số lượng ước phải là số nguyên tố lẻ: ~3, 5, 7, 11, \dots~).

Hạnh Phúc nhìn dãy số nhảy múa trên bảng cùng thời gian trôi qua từng giây, hoàn toàn bối rối, cậu không thể tính tay hàng triệu phép chia chỉ trong vài nhịp thở. Hạnh Phúc rất cần sự trợ giúp của bạn, lập trình viên tài năng, cậu ấy nhờ đến các bạn lập trình để giải bài toán của Giáo sư.

Yêu cầu: Hãy viết một chương trình tối ưu để xử lý trọn vẹn các yêu cầu của Giáo sư, giúp Hạnh Phúc vượt qua thử thách cam go này nhé!

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

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

Scoring

Sample Input 1

5
12 400
412 1000
32 100
1910 3000
1 100

Sample Output 1

82
93
17
141
32