An đang bị phạt và cô gáo đang để 1 chiếc đồng hồ đếm giây ở cạnh An để tính thời gian phạt.

Hiện giờ đồng hồ đang đếm x giây. Sau 1 giây nữa, số chỉ sẽ tăng lên x+1. Tuy nhiên, An biết loại đồng hồ đếm giây này có 1 lỗ hổng cho phép An làm số chỉ thay đổi ngay lập tức x thành x' ở đó x' là số bé nhất không nhỏ hơn x mà chia hết cho y. Thời gian thực hiện thao tác làm thay đổi chỉ số này coi như bằng 0. An sẽ lợi dụng lỗ hổng này để thời gian  trôi nhanh hơn. 

Để tránh cô giáo phát hiện, an sẽ hack vào lỗ hổng không quá k lần. 

Vậy sau t giây nữa, số chỉ lớn nhất của đồng hồ là bao nhiêu?

Ví dụ, x = 9, y = 10, k =10 và t = 2. An có thể ngay lập tức hack để tăng số chỉ lên 10. Sau 1 giây, đồng hồ chỉ 11 giây, An hack ngay lập tức để đồng hồ chỉ 20 giây. Sau 1 giây nữa, đồng hồ chỉ 21 giây, Anh háck lần hai để đồng hồ chỉ 30 giây. Vậy sau t = 2 giây, đồng hồ chỉ 30 giây. Đây là số chỉ lớn nhất có thể đạt được.

Dữ liệu: 

- Dòng đầu tiêu chứa số nguyên n (1<= n <=10.000) là số lượng test. Sau đó là n test.

- Mỗi test gồm 1 dòng duy nhất chứa 4 số nguyên x,y,k và t (1<=x,y,k,t <=1.000.000.000)

Kết quả:

Với mỗi test ghi ra 1 số nguyên duy nhất là số  chỉ lớn nhất trên đồng hồ sau t giây trên 1 dòng

input	output
2 2 6 1 3 9 10 10 2	9 30