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;
char conver(int a) {
  char r;
  r = a + '0';
  return r;
}
int main() {
  int a, b, c, cont2 = 0, cont5 = 0;
  cin >> a >> b >> c;
  if (a > b) {
    a = a - (a / b) * b;
  }
  int r;
  char decimales[400];
  int f = 250, k = 1, t = 0;
  int aux = b;
  while (aux % 2 == 0) {
    aux = aux / 2;
  }
  while (aux % 5 == 0) {
    aux = aux / 5;
  }
  if (aux > 1) {
    f = 250 + max(cont2, cont5);
  }
  int con;
  do {
    con = 0;
    while (a < b && a > 0) {
      a = a * 10;
      con++;
      if (con > 1) {
        decimales[k] = '0';
        if (conver(c) == decimales[k]) {
          cout << k << endl;
          return 0;
        }
        k++;
      }
    }
    r = a % b;
    decimales[k] = conver((a - r) / b);
    if (conver(c) == decimales[k]) {
      cout << k << endl;
      return 0;
    }
    k++;
    a = r;
  } while (f--);
  cout << "-1" << endl;
  return 0;
}
