Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Position in Fraction

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou have a fraction . You need to find the first occurrence of digit *c* into decimal notation of the fraction after decimal point.

Input

The first contains three single positive integers *a*, *b*, *c* (1 ≤ *a* < *b* ≤ 10^{5}, 0 ≤ *c* ≤ 9).

Output

Print position of the first occurrence of digit *c* into the fraction. Positions are numbered from 1 after decimal point. It there is no such position, print -1.

Examples

Input

1 2 0

Output

2

Input

2 3 7

Output

-1

Note

The fraction in the first example has the following decimal notation: . The first zero stands on second position.

The fraction in the second example has the following decimal notation: . There is no digit 7 in decimal notation of the fraction.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/13/2018 17:40:29 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|