Ngồi trong quán net, Protoype huých vai Lam2012 rồi chỉ vào màn hình: "Mày thấy hội Mặt Nạ Hành Xác này chưa? Bọn nó thề không độc thân, ít nhất phải có 2 ước nguyên tố mới chịu chơi. Nhưng cái nết thì cực hãm: gọi \(P\) là tích và \(S\) là tổng các ước nguyên tố phân biệt, thì \(P\) phải chia hết cho \(S\), mà chia xong kết quả \(Q = P/S\) lại phải lộn về làm một số nguyên tố thì mới chịu chốt đơn." Lam2012 nhìn cái giới hạn \(5 \cdot 10^6\) mà muốn sút cho thằng bạn một phát vì cái tội bắt CPU hóa vàng để duyệt trâu. Protoype chỉ cười khà khà: "Dùng não mà nặn số đi con trai, cái hội biến thái này hiếm tới mức đếm chưa hết bàn tay đâu!"

Yêu cầu: Cho đoạn \([L, R]\), hãy đếm các số nguyên dương \(n\) thỏa mãn:

• \(n\) có ít nhất \(2\) ước nguyên tố phân biệt.
• Gọi \(P\) là tích, \(S\) là tổng các ước nguyên tố phân biệt của \(n\). Ta có \(P\) chia hết cho \(S\) và \(Q = P/S\) là một số nguyên tố.

Input

• Dòng đầu tiên chứa số nguyên \(T\) (\(1 \le T \le 10^5\)) — số lượng bộ test.
• \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L\) và \(R\) (\(1 \le L \le R \le 5 \cdot 10^6\)).

Output

• Với mỗi bộ test, in ra một số nguyên duy nhất là số lượng số "Siêu Hiếm" trong đoạn \([L, R]\).

Example

3
1 30
30 30
1 1000

1
1
40

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(T \le 10, L, R \le 10^5\).
• Subtask \(2\) (\(25\%\) số điểm): \(T \le 10, L, R \le 5 \cdot 10^6\).
• Subtask \(3\) (\(25\%\) số điểm): \(T \le 10^5, L, R \le 10^5\).
• Subtask \(4\) (\(25\%\) số điểm): Không có ràng buộc gì thêm.