Ước nguyên tố

Xem PDF

Nộp bài


Điểm: 10 (thành phần)
Thời gian: 1.0s
Bộ nhớ: 256M

Tác giả:
Dạng bài

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\).