Cho $t$ truy vấn, mỗi truy vấn gồm 3 số nguyên dương $a,b,n$. Hãy tìm số nguyên dương thứ $n$ chia hết cho $a$ hoặc $b$.

• Dòng đầu chứa số nguyên $t$ $(t\le {10}^3)$
• $t$ dòng tiếp theo, mỗi dòng là bộ 3 số nguyên dương $a,b,n(a,b,n\le {10}^9)$

Kết quả: Gồm $t$ dòng là kết quả của $t$ test

Ví dụ:

Input

2
2 4 6
3 5 7

Output

12
15