900_B. Position in Fraction_28701
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. 
def convert(numerator, denominator):
    ans= str(numerator//denominator)+ "."
    l={}
    index=0
    numerator = numerator%denominator
    l[numerator]=index
    t=False
    while t==False:
        if numerator==0:
            break
        digit = numerator*10//denominator
        numerator=numerator*10-(numerator*10//denominator)*denominator
        if numerator not in l:
            ans+=str(digit) 
            index+=1
            l[numerator]=index
            t=False
        else:
            ans+=str(digit)+")"
            ans=ans[:l.get(numerator)+len(ans[:ans.index(".")+1])]+"("+ ans[l.get(numerator)+len(ans[:ans.index(".")+1]):]
            t=True
    return ans

n = raw_input().split(' ')
n = [int(i) for i in n]
a = n[0]
b = n[1]
c = n[2]
res = -1
f = 0
j = 1
k = a / b
drob = ""
s = convert(a, b)
if s.find("(") == -1:
    s = s + "0"
s = s.replace("0.", "")
s = s.replace("(", "")
res = s.find(str(c))
if res <> -1: res = res + 1
print res

2 3 7
 1 2 0
 1 10 1
 53 101 6
 567 1580 0
 69168 84860 4
 35 111 4
 99971 99989 0
 25102 31579 2
 13805 15538 3
 38790 39359 0
 2 3 0
 7 31 3
 1 9 0
 45 97 0
 1636 3269 6
 8 51 0
 1 3 0
 8880 81608 9
 1 7 7
 1 100 0
 1 100000 1
 1 57 0
 1 7 0
 1 2 5
 1 10001 9
 6873 7769 3
 4942 62768 5
 47117 78718 0
 99999 100000 8
 971 1883 3
 10958 21926 3
 44102 73848 2
 1 4 1
 69168 84860 8
 25102 57486 2
 13805 16262 3
 38790 64660 0
 7 30 3
 45 151 0
 1636 3269 9
 16 51 0
 13512 21926 3
 1 4 0
 1636 4367 9
 17650 21926 3
 558 1580 2
 8880 76242 0
 558 2062 3
 53 101 12
 567 1580 1
 35 111 8
 1 12 0
 8880 81608 0
 1 8 7
 1 57 1
 2 7 0
 1 11001 9
 433 7769 3
 47117 69358 0
 99999 100000 13
 971 1434 3
 1 3 7
 1 2 1
 558 1580 1
 69168 84860 1
 10757 57486 2
 10 30 3
 45 215 0
 13 51 0
 1 3 1
 8880 52919 0
 2 8 7
 1 22 1
 4 7 0
 367 7769 3
 47117 137344 0
 1649 100000 13
 627 1434 3
 1 3 5
 1 2 2
 2 4 0
 69168 84860 0
 10757 57486 4
 8 30 3
 68 215 0
 1636 4367 4
 13 65 0
 1 6 1
 2 14 7
 367 1552 3
 1649 100000 11
 778 1434 3
 1 2 3
 558 2062 2
 69168 103222 0
 8 23 3
 47 215 0
 1636 7762 4
 1 9 1
 14075 76242 0
 2 14 2
 367 1552 6
 778 1180 3
 50383 103222 0
 8 23 2
 47 215 1
 1 9 2
 14075 127808 0
 2 14 4
 367 3003 6
 778 1180 0

-1
 2
 1
 -1
 6
 107
 -1
 9
 174
 164
 212
 -1
 15
 -1
 39
 150
 10
 -1
 161
 6
 1
 5
 1
 -1
 1
 5
 163
 122
 213
 -1
 130
 117
 132
 -1
 1
 6
 20
 5
 2
 4
 10
 9
 41
 3
 8
 7
 12
 29
 22
 -1
 -1
 -1
 1
 2
 -1
 2
 -1
 5
 5
 6
 -1
 -1
 -1
 -1
 4
 2
 5
 1
 2
 5
 -1
 5
 -1
 -1
 -1
 5
 4
 -1
 2
 -1
 -1
 2
 4
 10
 -1
 7
 3
 2
 1
 6
 2
 -1
 5
 -1
 1
 3
 1
 5
 7
 1
 5
 3
 3
 4
 5
 5
 2
 -1
 3
 2
 -1
 7
