#include<bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back #define fi first #define se second typedef pair<ll,ll> P; using VP = vector<P>; using VVP = vector<VP>; using VI = vector<ll>; using VVI = vector<VI>; using VVVI = vector<VVI>; const int inf=1e9+7; const ll INF=1LL<<60; const ll Mod=998244353; void solve(ll a,ll b,ll c){ ll cnt=0; if(c==1) { cout<<-1<<endl; return; } while(a>=2*c-1){ if(a%c!=0){ a=a/c; cnt+=2; } else{ a=a/c; cnt++; } } if(a==0) cnt+=0; else if(a<=c-1) cnt++; else cnt+=2; cout<<b*cnt<<endl; } int main(){ int i,j; int q; cin>>q; for(int l=0;l<q;l++){ ll a,b,c; cin>>a>>b>>c; solve(a,b,c); } }