Anh ~T~ được sếp là chị ~B~ giao cho một hệ thống dữ liệu ~TYB~ sơ khai. Hệ thống này sẽ trả về True hay False tùy xem số nguyên dương ~X~ được truyền vào có phải là một số ~\text{PrimeBit}~ hay không.

Một số được gọi là ~\text{PrimeBit}~ nếu thỏa mãn:

• Biểu diễn ~X~ dưới dạng xâu nhị phân (không có các bit 0 vô nghĩa ở đầu).
• Mọi đoạn bit 1 liên tiếp đều có độ dài là một số nguyên tố.
• Ví dụ: 24 là một số ~\text{PrimeBit}~ vì ~24_{(10)} = 110111_{(2)}~ có hai đoạn bit 1 liên tiếp là ~[11]~ và ~[111]~ đều có độ dài tương ứng là 2 và 3 (là các số nguyên tố). Còn 23 không phải là số ~\text{PrimeBit}~ vì ~23_{(10)} = 10111_{(2)}~ có đoạn bit 1 liên tiếp đầu tiên là ~[1]~ có độ dài là 1 (không phải số nguyên tố).

Từ hệ thống dữ liệu ~TYB~ ở trên, anh ~T~ đã phát triển thêm khả năng: với một cấu hình bộ dữ liệu ~[L, R]~, hệ thống sẽ trả về số lượng số ~X~ là số ~\text{PrimeBit}~ thỏa mãn ~L \le X \le R~ theo modulo ~10^9 + 7~.

Hiện tại có ~N~ cấu hình bộ dữ liệu ~[L_i, R_i]~ cần xử lí. Nhiệm vụ của bạn là đưa ra kết quả cho mỗi cấu hình bộ dữ liệu ~[L_i, R_i]~.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương ~N~.
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~L_i~ và ~R_i~.

Dữ liệu ra

• In ra ~N~ dòng, dòng thứ ~i~ chứa một số nguyên duy nhất là số lượng số ~\text{PrimeBit}~ tìm được theo modulo ~10^9 + 7~.

Giới hạn

• ~1 \le N \le 100~.
• ~1 \le L_i \le R_i \le 10^{250}~ với mọi ~i = 1, 2, \dots, N~.

Subtask

• Subtask 1 (30% số điểm): ~1 \le L_i \le R_i \le 10^6~ với mọi ~i = 1, 2, \dots, N~.
• Subtask 2 (30% số điểm): ~10^9 \le L_i \le R_i \le 10^{18}~ với mọi ~i = 1, 2, \dots, N~.
• Subtask 3 (40% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Sample Input

3
1 10
20 100
1000 2000

Sample Output

3
13
87

Giải thích

• Trong ví dụ thứ nhất, cấu hình bộ dữ liệu ~[1, 10]~ gồm có 3 số ~\text{PrimeBit}~ là 3, 6, 9.
• Trong ví dụ thứ hai, cấu hình bộ dữ liệu ~[20, 100]~ gồm có 13 số ~\text{PrimeBit}~ là 24, 27, 28, 31, 48, 51, 54, 55, 56, 59, 62, 96, 99.