#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7; 
int n, t, a, b, res, m, k;
main() {
	for (scanf("%lld", &t); t; t -- ) {
		scanf("%lld%lld%lld%lld%lld", &n, &k, &m, &a, &b);
		if (k == 1) {
			if (n % m) printf("-1\n");
			else printf("0\n");
			continue;
		}
		res = 2e18;
		for (int i = 0; ~i; n /= k, i ++ ) {
			if (n == 0) {
				res = min(res, i * b);
				break;
			}
			__int128 l = n, r = n;
			int ans = i * b;
			while (l / m == r / m && l % m)
				l *= k, r = r * k + k - 1, ans += a;
			res = min(res, ans);
		}
		printf("%lld\n", res);
	}
}