#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<algorithm>
#include<vector>
#include<queue>
#include<list>
#include<string>
#include<set>
#include<map>
#include<iomanip>
#include<sstream>
#include<functional>
#include<climits>

const int mod = 1000007;
using namespace std;

const int N = 1000007;
long long dist[N], a, b, P, Q;
long long rev(long long x) {
  long long ret = 0;
  while (x) {
    long long b = x % 10;
    ret = ret*10 + b;
    x /= 10;
  }
  return ret;
}

void bfs() {
  queue<long long> q;
  q.push(a);
  memset(dist, -1, sizeof(dist));
  dist[a] = 0;
  while (!q.empty()) {
    long long cur = q.front();
    q.pop();
    long long y = (cur + P) % N, z = rev(cur * Q) % N;
    if (dist[y] == -1) {
      dist[y] = dist[cur] + 1;
      q.push(y);
    }
    if (dist[z] == -1) {
      dist[z] = dist[cur] + 1;
      q.push(z);
    }
  }
}
int main(){
  scanf("%d %d %d %d", &a, &b, &P, &Q);
  bfs();
  printf("%d\n", dist[b] + 1);
}