AlgoUniversity
  • Go Back
Discussion
Maths Equation :

Author

Akshay Sharma

Difficulty Level : Hard

Submissions : 83

Asked In : Tiktok

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

You need to login to view your submissions.

You need to login to view all submissions.

Loading...

Result : Executed

Loading...

Feel something is wrong with the test cases?

Result : Accepted

Test Cases :

You need to Log In
We're glad that you want to attempt this problem!

But to Run or Submit the Problem, you need to Log In.

Continue to Log In
Challenge Submitted!

Your challenge has been submitted successfully.

You will get a response soon via WhatsApp or Email.

Challenge
Facing issue while trying to solve the problem! Don't worry, we got you covered!

Do let us know your issue.

Looks good!
Please enter your issue / feedback.

How do we get in touch with you?
Looks good!
Please enter your phone no.
Looks good!
Please enter your email address.