Trung tâm \(XYZ\) có nhiệm vụ khảo sức mức độ phóng xạ của một khu vực nhiễm xạ gồm \(n\) địa điểm. Các địa điểm nằm trên một đường thẳng, được đánh số từ 1 đến \(n\) từ trái qua phải. Trung tâm sử dụng một robot để đo mức độ nhiễm xa.

Robot có khả năng nhận hai loại lệnh để di chuyển : Loại 1: di chuyển sang phải \(a\) bước; Loại 2: di chuyển sang trái \(b\) bước.

Cụ thể nếu robot đang đứng ở địa điểm \(v\), robot có thể thực hiện lệnh loại 1 để di chuyển đến địa điểm \(v+a\) nếu \(v+a<=n\), hoặc robot có thể thực hiện loại lệnh 2 để di chuyển đến địa điểm \(v-b\) nếu \(v-b>=1\). Khi robot dừng lại tại 1 địa điểm, robot có thể bật máy đo mức độ nhiễm xa và gửi kết quả thu được về trung tâm. Tuy nhiên do pin của robot có hạn , robot chỉ thực hiện được không quá \(k\) lệnh di chuyển. Ban đầu robot được đặt ở địa điểm 1.

Ví dụ, với \(n=6; a=2; b=3\) và \(k=3\) có thể sử dụng robot đo được mức độ nhiệm xạ tại các địa điểm, 1, 2, 3, 5 ( bao gồm địa điểm ban đầu của nó ). Như vậy robot không thể đo được mức độ nhiễm xạ tại các địa điểm 4 và 6.

Yêu cầu: Cho \(n, a, b\) và \(k\), hãy đếm số địa điểm mà robot không thể đo được mức độ nhiễm xạ.

Input

• Dòng đầu ghi số \(T ( 0 <T<10 )\) là số bộ dữ liệu có trong file;

• \(T\) dòng sau , mỗi dòng chứa 4 số nguyên dương \(n,a,b,k( a,b<=n<=10^9;k<=1000).\)

Output

• Gồm \(T\) dòng, mỗi dòng là số lượng địa điểm mà robot không thể đo được mức độ nhiễm xạ của bộ dữ liệu tương ứng.

Sample Input

2
6 2 3 3
100 99 1 100

Sample Output

2
0

Ràng buộc

• Có 50% số test có n<=1000.