#include <bits/stdc++.h>

#define int long long
#define ll __int128
#define ull unsigned long long
#define db double
#define ld long double
#define rep(i,l,r) for (int i = (int)(l); i <= (int)(r); ++ i )
#define rep1(i,l,r) for (int i = (int)(l); i >= (int)(r); -- i )
#define il inline
#define fst first
#define snd second
#define ptc putchar
#define Yes ptc('Y'),ptc('e'),ptc('s'),puts("")
#define No ptc('N'),ptc('o'),puts("")
#define YES ptc('Y'),ptc('E'),ptc('S'),puts("")
#define NO ptc('N'),ptc('O'),puts("")
#define pb emplace_back
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define get(x) ((x - 1) / len + 1)
#define debug() puts("------------------")

using namespace std;
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
typedef pair<ll,ll> PLL;
namespace szhqwq {
    template<class T> il void read(T &x) {
        x = 0; T f = 1; char ch = getchar();
        while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
        while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
        x *= f;
    }
    il int read() { int x; read(x); return x; }
    template<class T,class... Args> il void read(T &x,Args &...x_) { read(x); read(x_...); }
    template<class T> il void print(T x) {
        if (x < 0) ptc('-'), x = -x; 
        if (x > 9) print(x / 10); ptc(x % 10 + '0');
    }
    template<class T,class T_> il void write(T x,T_ ch) { print(x); ptc(ch); }
    template<class T,class T_> il void chmax(T &x,T_ y) { x = max(x,y); }
    template<class T,class T_> il void chmin(T &x,T_ y) { x = min(x,y); }
    template<class T,class T_,class T__> il T qmi(T a,T_ b,T__ p) {
        T res = 1; while (b) {
            if (b & 1) res = res * a % p;
            a = a * a % p; b >>= 1;
        } return res;
    }
    template<class T> il int getinv(T x,T p) { return qmi(x,p - 2,p); }
} using namespace szhqwq;
const int N = 2e5 + 10,inf = 1e9,mod = 998244353;
const ll inff = 1e18;
ll n,k,m,A,B;

il ll qmi(ll a,ll b) {
    ll sb = 1;
    while (b) {
        if (b & 1) sb = sb * a;
        a = a * a;
        b >>= 1;
    }
    return sb;
}

il bool check(ll x,ll mid) {
    ll aaaaa = qmi(k,mid);
    // write(aaaaa,' '); write(mid,'\n');
    ll now = x * aaaaa;
    if (now < m) return 0;
    if (now % m == 0) return 1;
    ll cnt = now / m + 1;
    while (1 + 1 == 2) {
        ll abab = cnt * m;
        if (abab - now < aaaaa) return 1;
        else break;
    }
    return 0;
}

il void solve() {
    //------------code------------
    read(n,k,m,A,B);
    if (n % m == 0) return puts("0"),void();
    if (k == 1) {
        if (n % m == 0) puts("0");
        else puts("-1");
        return ;
    }
    ll lim = log10(1.0 * n) / log10(1.0 * k) + 1;
    ll ans = inff,x = n;
    rep(c,0,100) {
        if (c) x /= k;
        if (x % m == 0) {
            chmin(ans,c * B);
            if (!x) break;
            continue;
        }
        // if (A == 100 && B == 1) cerr << c << " " << x << endl;
        ll l = 0,r,w = -1;
        if (x < m) r = max((ll)40,(ll)(log10(1.0 * m / x) / log10(1.0 * k) + (ll)2));
        else r = (ll)40;
        while (l <= r) {
            ll mid = l + r >> 1;
            // if (A == 100 && B == 1) cerr << " 324235rfsd " << mid << endl;
            if (check(x,mid)) r = mid - 1,w = mid;
            else l = mid + 1;
        }
        // if (A == 100 && B == 1) cerr << "w: " << w << endl;
        if (~w) chmin(ans,c * B + w * A);
    }
    if (ans != inff) write(ans,'\n');
    else puts("-1");
    // cerr << "Time : " << (db)(end - start) / CLOCKS_PER_SEC << " s" << endl;
    return ;
}

il void init() {
    return ;
}

signed main() {
    // freopen("transform.in","r",stdin);
    // freopen("transform.out","w",stdout);
    // init();
    int _ = 1;
    read(_);
    while (_ -- ) solve();
    return 0;
}