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. 
#include <bits/stdc++.h>
using namespace std;
inline int read() {
  register char c = ' ';
  register int v = 0, x = 1;
  while ((c < '0') || (c > '9')) {
    if (c == '-') x = -1;
    c = getchar();
  }
  while ((c >= '0') && (c <= '9')) {
    v = (v << 1) + (v << 3) + (c ^ 48);
    c = getchar();
  }
  return v * x;
}
inline void write(register int x) {
  if (x < 0) x = -x, putchar('-');
  if (x > 9) write(x / 10);
  putchar(x % 10 ^ 48);
}
int a, b, c, d;
inline int gcd(register int x, register int y) {
  return !y ? x : gcd(y, x % y);
}
int main() {
  a = read(), b = read(), c = read(), d = gcd(a, b);
  a /= d, b /= d, d = a / b, a -= b * d, a *= 10;
  for (register int i = 1; i <= 100000; i++) {
    d = a / b;
    a -= b * d;
    if (c == d) return write(i), ~~(0 - 0);
    a *= 10;
  }
  write(-1);
  return ~~(0 - 0);
}
