#include <bits/stdc++.h> using namespace std; #define lli long long int #define REP(i,s,n) for(int i=s;i<n;i++) #define MOD 1000000007 #define NUM 2520 #define INF (1LL<<50) #define DEBUG 0 #define mp(a,b) make_pair(a,b) #define SORT(V) sort(V.begin(),V.end()) lli b,c; lli calc(lli a){ lli next=0; if(c==1)return -1; while(1){ if(DEBUG)cout<<a<<endl; if(a<c){ next+=b; break; } if(a<=2*(c-1)){ next+= (2*b); break; } next+=b; if(a%c!=0)next+=b; a /= c; } return next; } void solve(){ lli a; cin>>a>>b>>c; /*逆からやるとよさそう*/ cout<<calc(a)<<endl; } signed main(){ lli q; cin>>q; REP(i,0,q)solve(); return 0; }