Maths Equation :
Difficulty Level : Hard
Submissions : 81
Asked In :
Marks :100
: 1 | : 0
Ram is having a maths exam tomorrow but today he is stuck in a problem that was related to maths equations. So he needs your help to solve the equation. Below is the equation that Ram is facing a problem to solve.
$$$$$$ (A*X)\%N=R $$$$$$
Help Ram to solve this equation by finding the minimum value of X. You are given A, R, N or print -1 if no answer exists.
Input
The first line of the test case contains a three integer A, R, N ($$$1 \le A \le R \le N \le 10^18$$$) — the integer value of the equation.
Output
For each test case print the minimum value of X which satisfies the equation If no such solution exists print -1.
Examples
Input
15 9 18
Output
3
Input
15 9 25
Output
-1
