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 sys import *
from collections import *
from math import *
from random import *
from datetime import date

def lStr(d = " "): return input().split(" ")
def lInt(d = " "): return [int(i) for i in input().split(d)]
def lDec(d = " "): return [float(i) for i in input().split(d)]

a, b, c = lInt()
i, f = 1, 1
check = set()

while a:
  d = 0

  if a >= b:
    if a in check:
      print(-1), exit(0)
    check.add(a)
    f = 1
    d, a = divmod(a, b)
  else:
    a *= 10
    
    if f:
      f = 0
      continue
  if d == c:
    print(i), exit(0)
  i += 1
print(i if c == 0 else -1)
