#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fup(a, b, c, d) for(int a = (b); a <= (c); a += (d))
#define fdo(a, b, c, d) for(int a = (b); a >= (c); a -= (d))
typedef long long ll;
typedef pair<int , int> PII;
typedef map<int , int> MII;
const int inf = 0x3f3f3f3f, N = 2e6 + 10, M = 4e5 + 10, mod = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int n, k, m, a, b;


void solve()
{
    cin >> n >> k >> m >> a >> b;
    
    if(k == 1) {
        if(n % m == 0) {
            cout << 0 << '\n';
        }
        else {
            cout << -1 << '\n';
        }
        return ;
    }
    if(n % m == 0) {
        cout << 0 << '\n';
        return ;
    }
    
    int nu = 1, su;
    int mi = INF;

    while(n) {
        su = nu * b;
        nu ++;
        n /= k;

        int l = n, r = n, nn = 1;
        while(1)
        {
            if(!(l % m)) break ;
            int bl = l / m + 1;
            if(bl * m <= r) break ;
            nn = nn * k % m;
            l = nn * n, r = (nn * (n + 1)) - 1;
            su += a;
        }

        mi = min(mi, su);
    }

    cout << mi << '\n';



    
}

signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int _ = 1;
    cin >> _;
    while(_ --)
    {
        solve();
    }
}