#include <bits/stdc++.h>

using namespace std;

#define int128 __int128_t
#define int long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fi first    
#define se second
#define lowbit(x) x & -x
#define all(x) x.begin(), x.end()
#define INF 0x3f3f3f3f3f3f3f3f
#define ls(x) x << 1
#define rs(x) x << 1 | 1
#define ull unsigned long long
std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e6 + 10, M = 5e6 + 10, mod = 998244353;
const double eps = 1e-8;

int t, n, m, k;	
string sr;

void solve() {
	int a, b;
	cin >> n >> k >> m >> a >> b;
	vector<PII> te;
	int temp = n, res = INF;
	if (k == 1) {
		if (n % m == 0) cout << 0 << "\n";
		else cout << -1 << "\n";
		return;
	}
	if (n % m == 0) {
		cout << 0 << "\n";
		return;
	}
	int step = 0;
	while (temp != 0) {
		temp /= k;
		step += b;
		if (temp == 0) res = min(res, step);
		else te.push_back({temp, step});
	}
	for (int i = 0; i < te.size(); i++) {
		int l = te[i].first, r = te[i].first, stp = te[i].second;
		while (true) {
			int num = l / m;
			int ri = (num + 1) * m;
			if (l % m == 0 || ri <= r) {
				res = min(res, stp);
				break;
			}
			l = l * k, r = r * k + k - 1;
			stp += a;
		}
	}
	cout << res << "\n";
}

signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	//cout.setf(ios::fixed), cout.precision(8);
	t = 1;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}