Nhập vào \(4\) số nguyên dương \(a,\ b,\ L,\ R\), cần đếm số lượng số nguyên trong đoạn \([a,\ b]\) chia hết cho ít nhất một số nguyên tố trong đoạn \([L,\ R]\).

Input

• Dòng thứ nhất chứa số nguyên dương \(T\): số lượng truy vấn.
• Tiếp theo là \(T\) dòng, mỗi dòng chứa \(4\) số nguyên dương theo thứ tự là \(a,\ b,\ L\) và \(R\).

Output

• Mỗi dòng in ra một số là kết quả của truy vấn tương ứng.

Ví dụ

Sample input

3
10 20 4 5
20 50 3 10
77 150 20 22

Sample output

3
17
0

Note

• Ở test case 3, vì trong đoạn \([20,\ 22]\) không có số nguyên tố nào nên kết quả trả về là \(0\).

Ràng buộc

• \(T\leq5000\);
• \(a\leq b,\ L\leq R\);
• \(b\leq10^{15}\);
• \(R\leq10^6,\ R-L\leq70\);
• Có \(40\%\) số test tương ứng với \(40\%\) số điểm có \(T\leq50\) và \(b-a\leq10^6\).