Mô tả và yêu cầu

Lam 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 Lam
quyết định thi vào lớp 10 chuyên Tin mà không thi vào lớp 10 chuyên Toán. Biết được
Lam sắp tới thi vào lớp 10 chuyên Tin nên Thầy giáo có bài tập về lập trình đố Lam 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ó hai số trùng nhau chỉ lấy một số) và sắp xếp chúng thành dãy tăng dần.
Yêu cầu: Tìm số thứ N trong dãy sau khi đã sắp xếp.
Dữ liệu: Vào từ thiết bị nhập chuẩn có cấu trúc:
 Dòng 1 chứa số nguyên dương T là số test (T ≤ 105);
 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 ≤ 105; N ≤ 2.109).
Kết quả: Ghi ra thiết bị xuất chuẩn gồm T dòng, mỗi dòng một số nguyên là kết quả một
test tương ứng.

Ví dụ

INPUT          OUTPUT                                    Giải thích
      3             28               Các bội nguyên dương của 4 hoặc 6 theo thứ tự sau
      4 6 9         15               khi sắp xếp là: 4, 6, 8, 12, 16, 18, 20, 24, 28…. Vậy
      2 3 10        6                số thứ 9 của dãy trên là 28
      3 3 2                          …
Ràng buộc:
       Có 20% số điểm tương ứng với số test có T = 1, a = b và N ≤ 2.109;
       Có 30% số điểm tương ứng với số test có T = 1, a ≠ b và N ≤ 104;
       Có 50% số điểm tương ứng với số test không còn ràng buộc gì thêm.