Cho 3 số nguyên dương \(a,b,n\). Tìm một số nguyên dương \(m\) nhỏ nhất sao cho:

• \(m\) không nhỏ hơn \(n\);

• \(m\) chia hết cho \(a\).

• \(m\) không chia hết cho \(b\).

Nếu không có số nguyên nào thỏa thì \(m = -1\).

Input

• Dòng đầu tiên chúa số nguyên \(t(t≤10^5)\)là số bộ test, với mỗi bộ test:

  • Gồm một dòng chứa 3 số nguyên \(a,b,n(a,b≤10^9,n≤10^{18} )\)

Đầu ra:

• In ra \(t\) số, mỗi số trên một dòng, là số \(m\) tìm được với bộ test tương ứng.

Sample Input

2
2 3 7
8 4 2

Sample Output

8
-1