/** * code generated by JHelper * More info: https://github.com/AlexeyDmitriev/JHelper * @author */ #include #include #ifndef SOLUTION_COMMON_H #include using namespace std; using ll = long long; using PI = pair; template using V = vector; using VI = V; #define _1 first #define _2 second #ifdef MY_DEBUG # define DEBUG(x) x #else # define DEBUG(x) #endif template inline void debug(T &A) { DEBUG( for (const auto &a : A) { cerr << a << " "; } cerr << '\n'; ) } template inline void debug_with_format(T &A, Func f) { DEBUG( for (const auto &a : A) { cerr << f(a) << " "; } cerr << '\n'; ) } template inline void debug_dim2(T &A) { DEBUG( for (const auto &as : A) { debug(as); } ) } template inline void debug(const char *format, Args const &... args) { DEBUG( fprintf(stderr, format, args ...); cerr << '\n'; ) } template string format(const string &fmt, Args ... args) { size_t len = snprintf(nullptr, 0, fmt.c_str(), args ...); vector buf(len + 1); snprintf(&buf[0], len + 1, fmt.c_str(), args ...); return string(&buf[0], &buf[0] + len); } template string fmtP(pair a) { stringstream ss; ss << "(" << a._1 << "," << a._2 << ")"; return ss.str(); } #define SOLUTION_COMMON_H #endif //SOLUTION_COMMON_H const int MOD = 1000000007; class B { public: void solve(std::istream& in, std::ostream& out) { int Q; in >> Q; for (int q = 0; q < Q; ++q) { int a, b, c; in >> a >> b >> c; if (c == 1) { out << "-1\n"; continue; } int cnt = 0; VI d; while(a > 0) { if (a % c > 0) cnt++; d.push_back(a % c); a /= c; } cnt += d.size() - 1; reverse(d.begin(), d.end()); if (d.size() >= 2 && d[0] == 1 && d[1] > 0 && d[1] < c - 1) cnt--; ll ans = ((ll)cnt) * b; out << ans << '\n'; } } }; int main() { B solver; std::istream& in(std::cin); std::ostream& out(std::cout); solver.solve(in, out); return 0; }