Bạn được cho 2 số nguyên dương \(a\) và \(b\).

Viết chương trình tìm số thứ \(n\) chia hết cho \(a\) hoặc \(b\).

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) (\(T \leq 100\)) - là số câu hỏi.
• \(T\) nhóm dòng tiếp theo, mỗi nhóm chứa 3 dòng chứa 3 số nguyên dương \(a, b, n\) (\(a, b \leq 10^4, n \leq 10^9\)).

Output

• Gồm \(T\) dòng, mỗi dòng chứa câu trả lời cho mỗi câu hỏi.

Example

1
2
3
10

15