You have a fraction <image>. 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 ≤ 105, 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: <image>. The first zero stands on second position.

The fraction in the second example has the following decimal notation: <image>. There is no digit 7 in decimal notation of the fraction. 
from decimal import Decimal, getcontext
getcontext().prec = 123456
o = input().split(" ")
a = Decimal(o[0])
b = Decimal(o[1])
c = Decimal(o[2])
d = str(a/b).split(".")
if len(d) == 2:
    d = d[1]
    for p, q in enumerate(d):
        if int(q) == int(c):
            if p == 123455:
                print(-1)
            else:
                print(p+1)
            exit()
    if int(c) == 0 and len(d) < 123456:
        print(len(d)+1)
        exit()
    print(-1)
    exit()
elif c == 0:
    print(1)
else:
    print(-1)
