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<=1e9;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.