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;
const int INFTY = 20000000;
const int MAX = 500100;
const int MOD = 10000000;
void coutTab(int* tab, int n) {
  for (int i = 0; i < n; i++) {
    cout << tab[i] << " ";
  }
  cout << "\n";
}
int findC(int a, int b, int c) {
  int i2 = 0, i5 = 0;
  int cb = b;
  while (b % 2 == 0) {
    i2++;
    b /= 2;
  }
  while (b % 5 == 0) {
    i5++;
    b /= 5;
  }
  b = cb;
  for (int i = 0; i < max(i2, i5); i++) {
    a *= 10;
    if (a / b == c) return i + 1;
    a = a % b;
  }
  a *= 10;
  int f = a / b;
  for (int i = 1; i < 10000; i++) {
    if (a / b == c) return max(i2, i5) + i;
    a = a % b;
    a *= 10;
  }
  return -1;
}
int main() {
  ios_base::sync_with_stdio(0);
  int a, b, c;
  cin >> a >> b >> c;
  cout << findC(a, b, c) << "\n";
}
