#include using namespace std; #define FOR(i, m, n) for(int (i) = (m); (i) < (n); (i)++) #define rep(i, n) FOR(i, 0, n) #define co(n) cout << (n) << endl #define cosp(n) cout << (n) << ' ' #define all(s) (s).begin(), (s).end() #define pb push_back #define mp make_pair #define fs first #define sc second typedef long long ll; typedef pair P; const ll INF = 1e9+1; const ll LINF = 1e18+1; const ll MOD = 1e9+7; //const ll MOD = 998244353; ll query(int a, int b, int c){ ll ans = 0; while(a){ if(a < c){ ans += b; a = 0; }else if(a < 2*c-1){ ans += b; a -= c-1; }else if(a%c){ ans += b; a -= a%c; }else{ ans += b; a /= c; } } return ans; } int main(void){ int q; cin >> q; rep(i, q){ int a, b, c; cin >> a >> b >> c; co(query(a, b, c)); } return 0; }