Chef đang cố gắng phát minh ra bóng đèn có thể chạy ở nhiệt độ phòng mà không cần điện. Anh ấy có N
khí đánh số từ 0 tới N – 1 mà anh ấy có thể dùng và anh ấy không biết khí nào trong N khí đó sẽ làm được
điều ấy, nhưng chúng ta lại biết.
Hiện Chef đã làm việc trên nhiều thuật toán tìm kiếm để tối ưu hóa việc tìm kiếm. Đối với dự án này, anh
ấy sử dụng thuật toán tìm kiếm dựa trên modulo do chính anh ấy phát minh ra. Vì vậy, đầu tiên anh ta
chọn một số nguyên K và chọn tất cả các chỉ số i theo thứ tự tăng dần sao cho i mod K = 0 và kiểm tra
các khí trên các chỉ số như vậy, rồi chọn tất cả chỉ số i theo thứ tự tăng dần mà i mod K = 1 rồi kiểm tra
những chỉ số đó, vân vân.
Cho N, chỉ số của khí p sẽ làm được và K, tìm xem sau bao lâu thì anh ấy sẽ cho Chefland thấy phát minh
mới, giả sử việc kiểm tra 1 khí hết 1 ngày.
Ví dụ, cho N = 5, p = 2 và K = 3.
Trong ngày thứ 1, Chef kiếm tra khí ga chỉ số 0 bởi 0 mod 3 = 0.
Trong ngày thứ 2, Chef kiểm tra khí ga chỉ số 3 bởi 3 mod 3 = 0.
Trong ngày thứ 3, Chef kiểm tra khí ga chỉ số 1 bởi 1 mod 3 = 1.
Trong ngày thứ 4, Chef kiểm tra khí ga chỉ số 4 bởi 4 mod 3 = 1.
Trong ngày thứ 5, Chef kiểm tra khí ga chỉ số 2 bởi 2 mod 3 = 2.
Sau 5 ngày, Chef có thể cho Chefland thấy phát minh mới.
Dữ liệu vào
Dòng đầu tiên của chứa một số nguyên T – số test. T test được mô tả như sau:
Dòng đầu tiên và duy nhất của mỗi test chứa ba số nguyên N, p và K.
Dữ liệu ra
Với mỗi test, in ra một dòng chứa một số nguyên – sau bao lâu Chef sẽ cho Chefland thấy phát
minh mới mà việc kiểm tra 1 khí hết 1 ngày
Ràng buộc
1 ≤ T ≤ $10^{5}$
1 ≤ N, K ≤ $10^{9}$
0 ≤ p < N
August Challenge 2021
Subtasks
Subtask #1 (100 điểm): Các ràng buộc gốc.
Ví dụ
Input
4
10 5 5
10 6 5
10 4 5
10 8 5
Output
2
4
9
8
Giải thích
Ví dụ 1: Vào ngày 1, Chef sẽ kiểm tra khí ga 0 và ngày 2 Chef kiểm tra khí ga 5.
Ví dụ 2: Vào ngày 1 Chef sẽ kiểm tra khí ga 0, vào ngày 2 Chef kiểm tra khí ga 5, vào ngày 3 Chef sẽ
kiểm tra khí ga 1, và ngày 4 Chef kiểm tra khí ga 6.
Ví dụ 3: Vào ngày 1 Chef kiểm tra khí ga 0, vào ngày 2 Chef kiểm tra khí ga 5, vào ngày 3 Chef kiểm tra
khí ga 1, ngày 4 Chef kiểm tra khí ga 6, vào ngày 5 Chef kiểm tra khí ga 2, vào ngày 6 Chef kiểm tra khí
ga 7, vào ngày 7 Chef kiểm tra khí ga 3, vào ngày 8 Chef kiểm tra khí ga 8, và ngày 9 Chef kiểm tra khí
ga 4.
Ví dụ 4: Vào ngày 1 Chef kiểm tra khí ga 0, vào ngày 2 Chef kiểm tra khí ga 5, vào ngày 3 Chef kiểm tra
khí ga 1, vào ngày 4 Chef kiểm tra khí ga 6, vào ngày 5 Chef kiểm tra khí ga 2, vào ngày 6 Chef kiểm tra
khí ga 7, vào ngày 7 Chef kiểm tra khí ga 3, và vào ngày 8 Chef kiểm tra khí ga 8. $x^{5}$
