Trong một cửa hàng có ~N + 1~ sản phẩm được đánh số thứ tự từ ~0~ đến ~N~. Mỗi sản phẩm có một màu sắc trong ~K~ màu. Màu của sản phẩm được ký hiệu bởi một số nguyên xác định bằng phần dư khi lấy số thứ tự của sản phẩm chia cho ~K~.

Chủ cửa hàng muốn sắp xếp các sản phẩm theo một trong hai phương án sau:

Phương án 1:

• Bộ các sản phẩm có số thứ tự chia ~K~ dư ~0~ xếp đầu tiên;

• Tiếp theo là bộ các sản phẩm có số thứ tự chia ~K~ dư ~1~;

• ~\dots~

• Bộ các sản phẩm có số thứ tự chia ~K~ dư ~K - 1~;

Phương án 2:

• Bộ các sản phẩm có số thứ tự chia ~K~ dư ~X~ xếp đầu tiên;

• Tiếp theo là bộ các sản phẩm có số thứ tự chia ~K~ dư ~X + 1~;

• ~\dots~

• Bộ các sản phẩm có số thứ tự chia ~K~ dư ~K - 1~;

• Bộ các sản phẩm có số thứ tự chia hết cho ~K~;

• Bộ các sản phẩm có số thứ tự chia ~K~ dư ~1~;

• ~\dots~

• Bộ các sản phẩm có số thứ tự chia ~K~ dư ~X - 1~.

Trong mỗi bộ sản phẩm cùng màu, các sản phẩm được sắp xếp giảm dần theo số thứ tự.

Chú ý: Dãy sau khi sắp xếp các số được đánh thứ tự từ ~1~ đến ~N + 1~.

Yêu cầu: Với ba số nguyên không âm ~N, K, X~ và số nguyên dương ~D~ ~(D \le N + 1)~. Tìm số thứ ~D~ của dãy số sau khi sắp xếp.

Input

• Dòng đầu tiên chứa số nguyên dương ~Q~ không vượt quá ~10^6~ là số lượng truy vấn;

• ~Q~ dòng tiếp theo, mỗi dòng mô tả một truy vấn có dạng: ~N, K, X, D~ ~(0 \le X < K < N \le 10^{18})~.

Output

Gồm ~Q~ dòng, dòng ~i~ chứa kết quả của truy vấn ~i~.

Chú ý: Nếu ~X = 0~ thì xếp theo phương án ~1~, ~X > 0~ xếp theo phương án ~2~.

Scoring

Sample Input 1

2
10 4 2 5
10 3 0 6

Sample Output 1

3
7

Notes

Với ~N = 10, K = 4, X = 2, D = 5~.

Các số ~10, 6, 2~ chia ~4~ dư ~2~; các số ~7, 3~ chia ~4~ dư ~3~; các số ~8, 4, 0~ chia hết cho ~4~; các số ~9, 5, 1~ chia ~4~ dư ~1~.

Dãy số sau khi sắp xếp là: ~10, 6, 2, 7, 3, 8, 4, 0, 9, 5, 1~.

Số thứ ~5~ là ~3~.

Tương tự: Với ~N = 10, K = 3, X = 0, D = 6~.

Dãy số sau khi sắp xếp là: ~9, 6, 3, 0, 10, 7, 4, 1, 8, 5, 2~.

Số thứ ~6~ là ~7~.