Cho ba số nguyên không âm ~N, K, X~. Với dãy số ~0, 1, 2, 3, \dots, N~ người ta sắp xếp lại dãy số đó theo quy tắc:

• Đầu tiên là bộ các số chia ~K~ dư ~X~;

• Tiếp theo là bộ các số chia ~K~ dư ~X + 1~;

• ~\dots~;

• Tiếp theo là bộ các số chia ~K~ dư ~K - 1~;

• Tiếp theo là bộ các số chia hết cho ~K~;

• Tiếp theo là bộ các số chia ~K~ dư ~1~;

• ~\dots~;

• Cuối cùng là bộ các số chia ~K~ dư ~X - 1~.

Trong mỗi bộ số có cùng tính chia hết, các số được sắp xếp giảm dần.

Ví dụ: ~N = 10, K = 4, X = 2~.

• Ta có: bộ các số chia ~4~ dư ~2~ là ~10, 6, 2~; bộ các số chia chia ~4~ dư ~3~ là ~7, 3~; bộ các số chia hết cho ~4~ là ~8, 4, 0~; bộ các số chia ~4~ dư ~1~ là ~9, 5, 1~;

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

Yêu cầu: Cho ~Q~ truy vấn, mỗi truy vấn chứa ba số nguyên không âm ~N, K, X~ và số nguyên dương ~D~. 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 gồm bốn số ~N, K, X, D~ ~(0 \le X < K < N \le 10^{18}, D \le N + 1)~.

Output

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

Scoring

Sample Input 1

2
10 4 2 5
10 3 0 6

Sample Output 1

3
7

Notes

Trong truy vấn thứ hai: ~N = 10, K = 3, X = 0~.

• 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~.