Cho ba số nguyên không âm ~N, K, X~. Với dãy số ~0, 1, 2, 3, \dots, N~ 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 sẽ chia dãy số ban đầu thành các bộ số như sau:

  • Bộ các số chia ~4~ dư ~2~ là ~10, 6, 2~;
  • Bộ các số 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 Specification: Data taken from DCH.INP

• Dòng đầu tiên chứa số nguyên dương ~Q~ ~(0 \le Q \le 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 Specification: Data written in DCH.OUT

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

Limitations

• Có ~50\%~ số Cases ứng với ~50\%~ số điểm thỏa mãn: ~Q, N \le 10^3~;
• Có ~30\%~ số Cases khác ứng với ~30\%~ số điểm thỏa mãn: ~X = 0; Q \le 10^5~;
• ~20\%~ số Cases còn lại ứng với ~20\%~ số điểm không có ràng buộc gì thêm.

Sample Case(s)

Input #1:

2
10 4 2 5
10 3 0 6

Output #1:

3
7

Explanation:

• Truy vấn ~1~: Đã giải thích ở đề bài.
• Truy vấn ~2~: ~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~.