#include "bits/stdc++.h"
using namespace std;
#ifdef LOCAL
#include "bits/debug.h"
#else
#define debug(...) (void)0
#endif
using i64 = int64_t;
using u64 = uint64_t;
using i128 = __int128_t;

// 先除再乘，不然没有意义，因为如果先乘再除就把乘的东西完全除掉了
// 进行 p 次乘法操作后，n 的范围是 [k^p × n, k^p × (n + 1) − 1]，只要这个范围里面包括 m 的倍数即可停止乘法操作。因此乘法操作至多进行 logk m 次。
// 右边那一项推式子可以看出来

template <class T>
constexpr T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}

#define int i128

std::ostream &operator<<(std::ostream &os, i128 n) {
    std::string s;
    while (n) {
        s += '0' + n % 10;
        n /= 10;
    }
    std::reverse(s.begin(), s.end());
    return os << s;
}

void solve()
{
#define tests
    i64 n; i64 k, m, a, b; cin >> n >> k >> m >> a >> b;
    if (k == 1) {cout << (n == m ? 0 : -1) << "\n"; return ;}

    auto check = [&](int p, i128 n) {
        auto lo{power<i128>(k, p) * n}, hi{power<i128>(k, p) * (n + 1) - 1};
        for (const i128& trym : {(i128)(lo + m - 1) / m * m, (i128)hi / m * m}) if (trym >= lo and trym <= hi) {return true;}
        return false;
    };

    int pw{}; {
        auto now{n}; while (now > 0) {now /= k; pw += 1;} 
    }

    i128 ans{1LL * pw * b}, now{n}; for (int i = 0; i <= pw; i++, now /= k) {
        for (int p{}; ; p++) if (check(p, now)) {ans = min(ans, i * b + p * a); break ;}
    }

    cout << (i64)ans << "\n";

}

signed main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    i64 _ { 1 };
#ifdef tests
    cin >> _;
#endif
    while (_--) {solve();}
    return 0;
}