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