//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 0xccccccc;
const ll LINF = 0xcccccccccccccccLL;
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}



//head



int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;
  ll n;
  cin >> s >> n;
  ll u = *max_element(all(s))-'0';
  u++;
  int cnt = 0;
  int siz = s.size();
  if(siz == 1) {
    cout << (n >= stoi(s)) << endl;
    return 0;
  }
  if(siz == 2) {
    if(u*(s[0]-'0')+(s[1]-'0') > n) {
      cout << "0\n";
      return 0;
    }
    int s0 = s[0]-'0';
    int s1 = s[1]-'0';
    ll x = (n-s1)/s0;
    cout << x-u+1 << endl;
    return 0;
  }
  if(siz == 3) {
    ll s0 = s[0]-'0';
    ll s1 = s[1]-'0';
    ll s2 = s[2]-'0';
    if(s0*u*u+s1*u+s2 > n) {
      cout << "0\n";
      return 0;
    }
    __int128_t lb = u, ub = 1e9+100;
    while(ub != lb+1) {
      __int128_t mid = (lb+ub)/2;
      if(s0*mid*mid+s1*mid+s2 > n) ub = mid;
      else lb = mid;
    }
    cout << ll(ub-u) << endl;
    return 0;
  }
  while(true) {
    __int128_t k = 1, x = 0;
    rep(i, siz-1) {
      k *= u;
      if(k > n) goto OUT;
    }
    rep(i, siz) {
      x += k*(s[i]-'0');
      k /= u;
    }
    if(x > n) goto OUT;
    u++;
    cnt++;
  }
OUT:;
  cout << cnt << endl;
}
#include <bits/stdc++.h>
#include <numeric>
using namespace std;

#define int long long
#define FOR(i, size) for (int i = 0; i < size; i++)
#define all(x) x.begin(), x.end()
#define endl "\n"
#define MOD 1000000007

#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template <typename... Args>
void logger(string vars, Args &&...values)
{
	cout << vars << " = ";
	string delim = "";
	(..., (cout << delim << values, delim = ", "));
}

template <typename T>
void print_list(vector<T> collection, bool newline = true)
{
	for (const auto &item : collection)
	{
		cout << item << " ";
	}
	if (newline)
		cout << endl;
}

#define ONE_TESTCASE 1

int n, m, timer;

void Solve()
{
	int a, b, c, d;
	cin >> a >> b >> c >> d;

	int de = c * d - b;
	if (de <= 0)
	{
		cout << -1;
		return;
	}

	int ans = a / de;
	cout << (ans + (a % de == 0 ? 0 : 1));
}

int32_t main()
{

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

#if ONE_TESTCASE
	int test = 1;
#else
	int test;
	cin >> test;
#endif

	for (int t = 1; t <= test; t++)
	{
		Solve();
		cout << endl;
	}
}
