#include #include #include #include #include #include #include using namespace std; typedef long long ll; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; int Q; cin >> Q; for(int dum = 0; dum < Q; dum++){ ll A, B, C; cin >> A >> B >> C; ll ans = 0; if(C == 1){ ans = A*B; cout << ans << endl; return 0; } while(A != 0){ if(A <= 2*C-2){ if(A < C) ans += B; else ans += 2*B; break; } if(A%C != 0) ans += B; A -= (A%C); if(A != 0){ A /= C; ans += B; } } cout << ans << endl; } }