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 10^5)\) - là số câu hỏi.
• \(T\) dòng, mỗi 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