Chia hết và chia có dư

Cho \(3\) số nguyên dương \(a, b, n\).

Hãy tìm số nguyên dương \(k\) nhỏ nhất nhưng không nhỏ hơn \(n\) sao cho \(k\) chia hết cho \(a\) và \(k\) không chia hết cho \(b\).

Nếu không có số nguyên dương \(k\) nào thỏa mãn thì gán \(k = -1\).

Input

• Một dòng gồm \(3\) số \(a, b, n\), mỗi số cách nhau một dấu cách.
• Giới hạn:
  • \(1 \le a, b \le 10^9\)
  • \(1 \le n \le 10^{16}\)

Output

• Ghi ra kết quả bài toán.

Example

2 3 7

8

8 4 2

-1