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. 
#monsijb
from decimal import *
a,b,c = input().split()
#print(a,b,c)
a1 = int(a)
b1 = int(b)
c11 = int(c)
#print(a1+b1)
getcontext().prec=b1
c1 = Decimal(a1)/Decimal(b1)
c2 = str(c1)
q1 = b1 % 2
q2 = b1 % 5
if q1==0 or q2==0:
    c2 = c2 + "0"

#print(c2 + "HI")
#print(c2)
length = len(c2)

#print(c2)
b = 0
res = 0
j = 0
#print(type(c))
for i in range(length):
    #print(i)
    #print(b)
    #print(res)
    if c2[i] == ".":
        b=1
        j=0
    elif c2[i] == c and b==1:
        if c!=0 and j<b1:
            print(j)
            res=1
            break
        elif c11==0:
            print(j)
            res=1
            break
    j +=1
if res==0:
    print(-1)
        
