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. 
import sys

def long_division(dividend, divisor):
	ans = ""
	index = 0
	cur_dividend = int(str(dividend)[index:index + 1].ljust(1, "0"))
	dividends = set()
	while cur_dividend not in dividends:
		dividends.add(cur_dividend)
		div, mod = divmod(cur_dividend, divisor)
		yield div
		index += 1
		cur_dividend = mod
		cur_dividend = int(str(cur_dividend) + str(dividend)[index:index + 1].ljust(1, "0"))

	return None

def decimal_part(dividend, divisor):
	for i in long_division(dividend, divisor):
		if dividend == 0:
			yield i
		dividend //= 10

def solve(a, b, c):
	for index, v in enumerate(decimal_part(a, b)):
		if v == c:
			return index + 1
	return -1

print(solve(*map(int, input().split())))