Cho bốn số M, N, A, B. Nhiệm vụ của bạn là hãy đếm tất cả các số trong khoảng [M, N] chia hết cho các số A hoặc B.

Input

Dòng đầu tiên đưa vào số lượng test T.

Những dòng kế tiếp đưa vào các bộ test.

Mỗi bộ test gồm 4 số M, N, A, B. T, M, N, A, B thỏa mãn rang buộc 1≤T≤100; 1≤M ≤ N ≤10^9 ; 1≤A, B ≤1000;

Output

Đưa ra kết quả mỗi test theo từng dòng.

Example:

**Input**
2 
5 11 4 6
3 1000 5 9

Output
2
289