#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve(){

    int T;
    cin>>T;
    while(T--) {
        int n, k, m, a, b;
        cin >> n >> k >> m >> a >> b;

        if (k == 1) {
            if (n % m == 0) {
                cout << "0" << "\n";
            } else {
                cout << "-1" << "\n";
            }
            return;
        }
        int ans = 1000000000000;
        int cnt = 0;
        while (cnt*b<1000000000000) {
            int mod = n - n/m*m;
            int cost = cnt * b;
            int flag = 1;
            int range = 1;
            if (mod == 0) flag = 0;
            while (flag) {
                cost += a;
                mod *= k;
                mod %= m;
                range *= k;
                if (mod == 0 || mod + range - 1 >= m) flag = 0;
            }
            ans = min(ans, cost);
            n = n / k;
            cnt++;
        }
        cout << ans << "\n";
    }
}
signed main()
{
    int T;
    cin>>T;
    while(T--){
        solve();
    }
}