#include <bits/stdc++.h>
#define int long long
using namespace std;
const double eps = 1e-8;

void solve() {
    int n, k, m, a, b, res = 1e15, cur = 0;
    cin >> n >> k >> m >> a >> b;
    if(n % m == 0) {
        cout << 0 << '\n';
        return ;
    }
    if(k == 1) {
        cout << -1 << '\n';
        return ;
    }
    while(n) {
        int tmp = cur, len = 1, l = n % m, r = n % m;
        while(len < m && (l < r || l == r && l)) {
            tmp += a;
            len *= k;
            l = l * k % m;
            r = (r * k % m + k - 1) % m;
        }
        res = min(res, tmp);
        n = n / k;
        cur += b;
    }
    res = min(res, cur);
    cout << res << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);  cout.tie(0);
    int t = 1;  cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}