Cho bốn số nguyên \(L, R, a, b\). Hãy đếm số lượng các bội số của \(a\) hoặc \(b\) có giá trị thuộc đoạn \([L, R]\).

Đầu vào
Dòng đầu tiên của đầu vào chứa số nguyên \(T\) cho biết số bộ dữ liệu cần kiểm tra. Mỗi bộ dữ liệu gồm một dòng chứa 4 số nguyên \(L, R, a, b\)

Đầu ra
Ứng với mỗi bộ dữ liệu đầu vào, in ra một số là đáp án bài toán trên một dòng.

Ràng buộc
\(1 ≤T≤100; 1≤ L≤ R≤10^9; 1≤ a, b≤10^4\);

input

2
5 11 4 6
3 1000 5 9

output

2
289