Tìm số

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ó cho Lam một số bài tập về lập trình để Lam ôn thi 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 lần) 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.

Input

• Dòng đầu chứa số nguyên dương \(T\) (\(1 \le T \le 10^5\)) là số test;
• \(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 (\(1 \le a,b \le 10^5\), \(N \le 2 \cdot 10^9\)).

Output

Ghi ra \(T\) dòng, mỗi dòng một số nguyên là kết quả của một test tương ứng.

Input

%
3
4 6 9
2 3 10
3 3 2

Output

%
28
15
6

Notes

Các bội nguyên dương của \(4\) hoặc \(6\) theo thứ tự tăng dần là:

Vì vậy số thứ \(9\) của dãy trên là \(28\).

Scoring

• (20%) \(T = 1\), \(a = b\) và \(N \le 2 \cdot 10^9\);
• (30%) \(T = 1\), \(a \ne b\) và \(N \le 10^4\);
• (50%) Không có ràng buộc gì thêm.