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 short_division(dividend: int, divisor: int) -> (int, int):
    """
    This function returns a digit - remainder of the division
    Note that it is called only for the short division.
    """
    remainder = dividend
    quotient = 0
    while remainder >= divisor:
        remainder -= divisor
        quotient += 1
    return quotient, remainder
 
 
def long_division(dividend: int,
                  divisor: int,
                  number_of_digits,
                  target) -> (int, int):
    """
    Long division function
    """
    if divisor == 0:
        raise ZeroDivisionError("The divisor must be non-zero integer")
 
    if dividend == 0:
        return "0"
 
    positive = (dividend > 0 and divisor > 0) or (dividend < 0 and divisor < 0)
 
    # We are finding a quotient that closer to 0 than others,
    # not the least remainder (according to the Euclidean function) case
    absdividend = abs(dividend)
    absdivisor = abs(divisor)
 
    # initially the quotient is 0
    quotient = "0"
    # the point, from which we append a digit to the temporary divisor
    pointer = 0
    s = str(absdividend)
    # remainder is the result of substraction at the last step
 
    # max lenght of the period is equal to divisor by Dirichlet's principle
    period_length = absdivisor
    # the counter for the decimal separator
    # it's an analogue to the pointer variable but for the fractional step
    period_step = 0
 
    # Determine whether the fractional part started or not
    if absdividend >= absdivisor:
        period_started = False
        remainder = 0
    else:
        remainder = absdividend
        period_started = True
 
    # end if our fractional part become too long.
    # Unfortunately, we can't go forever
 
    is_found = False
 
    while period_step <= period_length and period_step < number_of_digits:
        if period_started:
            postfix = "0"
        else:
            postfix = s[pointer:pointer + 1]
 
        # the postfix is an empty string in case of complete division
        if not postfix:
            break
 
        remainder = int(str(remainder) + postfix)
        if remainder < absdivisor and not period_started:
            if 0 == target:
                is_found = True
                break
            quotient += "0"
            pointer += 1
            continue
        elif remainder < absdivisor and period_started:
            if 0 == target:
                is_found = True
                break
            quotient += "0"
            period_step += 1
            continue
 
        # just substruction-based division max value of quotint is 9
        temp_quotient, temp_remainder = short_division(remainder, absdivisor)
        quotient += str(temp_quotient)
        remainder = temp_remainder
 
        if temp_quotient == target:
            is_found = True
            break
 
        if remainder == 0 and period_started:
            period_step += 1
            break
        elif remainder == 0 and not period_started:
            # the code will break, if pointer will exceed the dividend
            pointer += 1
            continue
 
        if period_started:
            period_step += 1
        else:
            pointer += 1
 
        # three conditions to start the fractional part
        if remainder < absdivisor and not period_started and pointer >= len(s):
            period_started = True
 
    if is_found:
        return period_step + 1
    else:
        if target == 0:
            if period_step < period_length:
                return period_step + 1
        return -1
 
 
if __name__ == "__main__":
    s = input()
    a, b, c = [int(x) for x in s.split()]
 
    p = long_division(a, b, b, c)
    print(p)
