#include #include #include using namespace std; int main() { int Q; cin >> Q; while (Q--) { int A, B, C; cin >> A >> B >> C; if (C == 1) { cout << -1 << endl; } else { int ops = (A + C - 2) / (C - 1); vector seq = { A }; do { int x = seq.back(); seq.back() %= C; seq.push_back(x / C); int cost = int(seq.size()) - 1; for (int i : seq) { cost += (i + C - 2) / (C - 1); } ops = min(ops, cost); } while (C != 1 && seq.back() >= C); cout << 1LL * ops * B << endl; } } return 0; }