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 divide(a, b):
  assert b > 0
  integer = a // b
  remainder = a % b
  seen = {remainder: 0} 
  digits = []
  while(True):
    remainder *= 10
    digits.append(remainder // b)
    remainder = remainder % b
    if remainder in seen:
      where = seen[remainder]
      return (integer, digits[:where], digits[where:])
    else:
      seen[remainder] = len(digits)
x,y,z=map(int,input().split())
(i, f, r) = divide(x,y)
re=''.join(map(str,r))
fl=''.join(map(str, f))
st=""
for i in fl:
    if i.isdigit():
        st+=i
for i in re:
    if i.isdigit():
        st+=i
chk=str(z)
ans=st.find(chk)
if ans>=0:
    ans+=1
print(ans)