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 fractions import gcd
from math import factorial, ceil, sqrt, atan2
from itertools import *
import string
import copy
import random
from decimal import *
def id_generator(size=20, chars=string.digits):
    return ''.join(random.choice(chars) for _ in range(size))
 
def mp():
    return map(int,str(raw_input()).split())
getcontext().prec = 10000
a,b,c=mp()
z=Decimal(a)/Decimal(b)
j=1
z=str(z)[:1000]
if len(z)<1000:
	z+='0'
flag=0
#print z
for i in str(z)[2:]:
	if i==str(c):
		flag=1
		break
	j+=1
if flag:
	print j
else:
	print -1