Dãy chia hết

Cho ba số nguyên không âm \(N, K, X\) với \(0 \le X < K \le N\). Xét dãy số \(0, 1, 2, \dots, N\) và sắp xếp lại theo quy tắc sau:

• Trước hết là các số khi chia cho \(K\) có dư \(X\);
• Tiếp theo là các số khi chia cho \(K\) có dư \(X+1\);
• Tiếp theo là các số khi chia cho \(K\) có dư \(X+2\), …, \(K-1\);
• Tiếp theo là các số chia hết cho \(K\) (tức có dư \(0\));
• Tiếp theo là các số có dư \(1, 2, \dots, X-1\);

Trong mỗi nhóm các số có cùng số dư khi chia cho \(K\), các số được sắp xếp theo thứ tự giảm dần.

Yêu cầu. Có \(Q\) truy vấn. Mỗi truy vấn gồm bốn số \(N, K, X, D\).
Hãy tìm phần tử thứ \(D\) (đánh số từ \(1\)) trong dãy sau khi sắp xếp.

Input

Dòng đầu tiên chứa số nguyên dương \(Q\) (\(1 \le Q \le 10^6\)) là số lượng truy vấn.
\(Q\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(N, K, X, D\) với
\(0 \le X < K \le N \le 10^{18}\) và \(1 \le D \le N+1\).

Output

Gồm \(Q\) dòng, mỗi dòng in ra kết quả của một truy vấn.

Scoring

• (50%) \(Q, N \le 10^3\);
• (30%) \(X = 0\), \(Q \le 10^5\);
• (20%) Không có ràng buộc thêm.

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\).

Sample Input 1

2
10 4 2 5
10 3 0 6

Sample Output 1

3
7