Bài 4 (4 điểm): Tìm số

Bin là một học sinh giỏi Toán, nhưng lại có niềm đam mê về lập trình nên Bin quyết định thi và đỗ vào lớp 10 chuyên Tin. Thầy giáo ra bài test để cho Bin vào đội dự tuyển của trường như sau:

Cho hai số nguyên dương ~a~ và ~b~. Xét tất cả các số nguyên dương là bội của ~a~ hoặc ~b~ (nếu có số trùng nhau thì chỉ lấy một lần) và sắp xếp chúng theo thứ tự tăng dần. Yêu cầu: Tìm số thứ N trong dãy đã sắp xếp đó.

Dữ liệu vào gồm:

Dòng 1: chứa số nguyên dương ~T~ là số lượng test ~(T ≤ 10⁵)~.

~T~ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương ~a, b, N~ biểu thị cho một test ~(a, b ≤ 10⁵, N ≤ 2×10⁹)~.

Kết quả:

Gồm ~T~ dòng, mỗi dòng một số nguyên là kết quả của test tương ứng. Ví dụ:

Input:

3
4 6 9
2 3 10
3 3 2

Output:

28
15
6