Cột đèn bên đường ray

Một đoàn tàu chạy trên đường ray từ điểm $1$ đến điểm $L$ với tốc độ $1$ đơn vị độ dài mỗi phút (phút thứ nhất tàu ở điểm $1$, phút thứ hai ở điểm $2$, và cứ thế tiếp tục).

Dọc đường ray có các cột đèn đặt tại mọi điểm có tọa độ chia hết cho $v$: cột đèn thứ nhất ở điểm $v$, cột thứ hai ở điểm $2v$, và cứ thế tiếp tục.

Ngoài ra có đúng một đoàn tàu đang đứng yên, chiếm trọn các điểm từ $l$ đến $r$ (bao gồm cả hai đầu).

Hành khách nhìn thấy cột đèn ở điểm $p$ khi và chỉ khi $p$ chia hết cho $v$ và $p\notin [l,r]$. Nói cách khác, cột đèn nằm trong đoạn bị đoàn tàu đứng yên che khuất thì không nhìn thấy được.

Hãy đếm số cột đèn hành khách nhìn thấy trong suốt hành trình. Có $t$ truy vấn độc lập cần trả lời.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên $t$ là số truy vấn.
• $t$ dòng tiếp theo, dòng thứ $i$ chứa bốn số nguyên $L_i$, $v_i$, $l_i$, $r_i$ lần lượt là điểm đích của hành trình, chu kỳ đặt cột đèn, và đoạn bị đoàn tàu đứng yên chiếm giữ.

Dữ liệu ra

In ra $t$ dòng, dòng thứ $i$ chứa một số nguyên là đáp án cho truy vấn thứ $i$.

Ràng buộc

• $1\le t\le {10}^4$
• $1\le L_i,v_i\le {10}^9$
• $1\le l_i\le r_i\le L_i$

Ví dụ