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;
long long int check(int, int, int);
int fraction_to_decimal(int num1, int num2) {
  string res;
  map<int, int> mp;
  mp.clear();
  int rem = (num1 / num2);
  while ((rem != 0) && (mp.find(rem) == mp.end())) {
    mp[rem] = res.length();
    rem = rem * 10;
    int res_part = rem / num2;
    res += to_string(res_part);
    rem %= num2;
  }
  if (rem == 0) {
    return -1;
  }
  return res.size();
}
int main() {
  int a, b;
  cin >> a >> b;
  int c;
  cin >> c;
  cout << check(a, b, c);
  return 0;
}
long long int check(int a, int b, int c) {
  vector<int> arr;
  bool flag = true;
  int l = (fraction_to_decimal(a, b));
  if (l == -1) {
    l = 10000;
  }
  for (int i = 0; i <= l && (a != 0 || flag); i++) {
    a *= 10;
    if (a == 0) {
      flag = false;
    }
    int m = (a / b);
    if (m == c) {
      return arr.size() + 1;
    } else {
      arr.push_back(m);
      a -= (m * b);
    }
  }
  return -1;
}
