#include #define rep(i,n) for(int i=0;i P; const ll INF = 1e18; const int MOD = 1000000007; void solve(){ ll a,b,c; cin >> a >> b >> c; if(c==1){ cout << -1 << endl; return; } ll cnt = 0; while(a>0){ if(a%c == 0){ a /= c; cnt ++; }else{ if(a < c) a -= c,cnt ++; else if(c+1<= a && a<=2*(c-1) && c != 2) a = 0,cnt += 2; else{ a -= a%c; cnt ++; } } } cout << b*cnt << endl; return; } int main(){ int q; cin >> q; while(q--){ solve(); } return 0; }