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

Input

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

Output

• Ứ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.

Constraints

• \(1 \le T \le 100\)
• \(1 \le L \le R \le 10^9\)
• \(1 \le a, b \le 10^4\)

Example

2
5 11 4 6
3 1000 5 9

2
289