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