Lucky Step

Little Z stands at position \(b\) on the number line and begins moving along the positive direction. Every step, she immediately moves \(a\) units forward, so her new position becomes \(an+b\) after \(n\) steps. Her lucky number is a positive integer \(c\); she considers a position lucky if it is coprime with \(c\), i.e. if \(\gcd(an+b, c)=1\). Given three positive integers \(a\), \(b\), and \(c\), determine whether there exists a non-negative integer \(n\) such that \(\gcd(an+b, c)=1\). If such an \(n\) exists, output any one valid \(n\); otherwise, output -1.

inputFormat

The input consists of three positive integers \(a\), \(b\), and \(c\) separated by spaces.

outputFormat

If there exists a non-negative integer \(n\) such that \(\gcd(an+b, c)=1\), output any one such \(n\); otherwise, output -1.

sample

4 3 2

0