Số square-free là số nguyên dương không có ước lớn hơn ~1~ nào là số chính phương cả. Chẳng hạn ~1,10,15,30~ là square-free nhưng ~12,18,25~ thì không. Cho hai số nguyên dương ~L, R~ với ~1 \le L \le R \le 10^7~, yêu cầu đếm số lượng số square-free lớn hơn ~1~, chỉ có ước nguyên tố lấy trong đoạn từ ~L~ đến ~R~.

Input

Dòng đầu tiên gồm số ~t~ là số test với ~1 \le t \le 3.~

Các dòng tiếp theo gồm các cặp ~(L,R)~.

Output

Ứng với mỗi test, cho biết số lượng số square-free thỏa mãn, vì kết quả có thể rất lớn nên lấy modulo ~10^9 + 7.~

Sample input

2
1 4
20 25

Sample output

3
1

Giải thích trong VD1, các số square-free thỏa mãn là: ~2,3,6~, còn trong VD2, chỉ có ~23~ thỏa mãn.