// problem: 
// date: 
#include <bits/stdc++.h>
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define SP << " " <<
#define fish signed
using namespace std;
const int INF = 0x3f3f3f3f3f3f3f3f;
int n, m, k, a, b;
double logk;
int qpow(int a, int b, int mod)
{
    int res = 1 % mod;
    while(b)
    {
        if(b & 1) res = res * a % mod;
        a = a * a % mod, b >>= 1;
    } return res;
}
bool check(int x)
{
    int tp = (m - n % m * qpow(k, x, m) % m) % m;
    return floor(log(tp) / logk) + 1 <= x;
}
void solve()
{
    cin >> n >> k >> m >> a >> b;
    logk = log(k);
    int cnt = 0, up = floor(log(m) / logk) + 1, ans = INF;
    while(n)
    {
        if(n % m == 0) {chmin(ans, cnt * b); break;}
        int l = 0, r = up, res = up + 1;
        while(l <= r)
        {
            int mid = l + r >> 1;
            if(check(mid)) r = mid - 1, res = mid;
            else l = mid + 1;
        }
        if(res <= up) chmin(ans, res * a + cnt * b);
        n /= k, cnt ++;
        if(k == 1)
            return cout << (ans == INF ? -1 : ans) << "\n", void();
    }
    chmin(ans, cnt * b);
    cout << (ans == INF ? -1 : ans) << "\n";
}
fish main()
{
    freopen("transform.in", "r", stdin);
    freopen("transform.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t --) solve();
    return 0;
}