#include "bits/stdc++.h" #define in std::cin #define out std::cout #define rep(i,N) for(LL i=0;i> Q; std::vectorA(Q), B(Q), C(Q); rep(i, Q) in >> A[i] >> B[i] >> C[i]; rep(i, Q) { if (C[i] == 1) out << -1 << std::endl; else { LL cnt = 0, t = A[i], ans = 1145148101919; while (t > 0) { if (t % C[i] == 0) { t /= C[i]; ++cnt; } else { ans = std::min(ans, cnt + (t + C[i] - 1) / C[i]); t -= t % C[i]; ++cnt; } } ans = std::min(ans, cnt); out << ans * B[i] << std::endl; } } }