#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++) #define rep(i, n) repr(i, 0, n) #define reprrev(i, a, b) for (int i = (int)(b)-1; i >= (int)(a); i--) #define reprev(i, n) reprrev(i, 0, n) #define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++) #define chmin(mi, value) mi = min(mi, value) #define chmax(ma, value) ma = max(ma, value) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define mp make_pair #define mt make_tuple #define INF 1050000000 #define INFR INT_MAX #define INFL (long long)(4e18) #define INFLR LLONG_MAX #define EPS (1e-10) //#define MOD 1000000007 #define MOD 998244353 #define PI 3.141592653589793238 #define RMAX 4294967295 using vi = vector; using vvi = vector>; using vvvi = vector>>; using vvvvi = vector>>>; using ll = long long; using vll = vector; using vvll = vector>; using vvvll = vector>>; using vd = vector; using vvd = vector>; using vb = vector; using vvb = vector>; using vc = vector; using vvc = vector>; using vs = vector; using vvs = vector>; using Pi = pair; using vPi = vector; using vvPi = vector>; using vvvPi = vector>>; using vvvvPi = vector>>>; using Pll = pair; using vPll = vector; using Pd = pair; using vPd = vector; template using vec = vector; template using pql = priority_queue, greater>; using Comp = complex; // vvvvvvvvvvvvvvvvvvvvvvv debug output vvvvvvvvvvvvvvvvvvvvvvv // vector input template istream &operator>>(istream &is, vector &vec) { for (T &x : vec) is >> x; return is; } // pair template ostream &operator<<(ostream &os, const pair &pair_var) { os << "(" << pair_var.first << ", " << pair_var.second << ")"; return os; } // vector template ostream &operator<<(ostream &os, const vector &vec) { os << "{"; for (int i = 0; i < vec.size(); i++) { os << vec[i] << (i + 1 == vec.size() ? "" : ", "); } os << "}"; return os; } // deque template ostream &operator<<(ostream &os, const deque &vec) { os << "{"; for (int i = 0; i < vec.size(); i++) { os << vec[i] << (i + 1 == vec.size() ? "" : ", "); } os << "}"; return os; } // map template ostream &operator<<(ostream &os, const map &map_var) { os << "{"; repi(itr, map_var) { os << *itr; itr++; if (itr != map_var.end()) os << ", "; itr--; } os << "}"; return os; } // set template ostream &operator<<(ostream &os, const set &set_var) { os << "{"; repi(itr, set_var) { os << *itr; itr++; if (itr != set_var.end()) os << ", "; itr--; } os << "}"; return os; } // multiset template ostream &operator<<(ostream &os, const multiset &set_var) { os << "{"; repi(itr, set_var) { os << *itr; itr++; if (itr != set_var.end()) os << ", "; itr--; } os << "}"; return os; } #define DUMPOUT cerr void dump_func() { DUMPOUT << endl; } template void dump_func(Head &&head, Tail &&... tail) { DUMPOUT << head; if (sizeof...(Tail) > 0) { DUMPOUT << ", "; } dump_func(std::move(tail)...); } #ifdef DEBUG_ #define DEB #define dump(...) \ DUMPOUT << " " << string(#__VA_ARGS__) << ": " \ << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]" \ << endl \ << " ", \ dump_func(__VA_ARGS__) #else #define DEB if (false) #define dump(...) #endif // ^^^^^^^^^^^^^^^^^^^^^^^ debug output ^^^^^^^^^^^^^^^^^^^^^^^ string YN(bool y, int id = 0) { if (id) cout << id; return (y ? "YES" : "NO"); } string yn(bool y, int id = 0) { if (id) cout << id; return (y ? "Yes" : "No"); } string ON(bool y, int id = 0) { if (id) cout << id; return (y ? "OK" : "NG"); } int dir4[4][2] = {{0, -1}, {-1, 0}, {1, 0}, {0, 1}}; int dir8[8][2] = {{-1, -1}, {0, -1}, {1, -1}, {-1, 0}, {1, 0}, {-1, 1}, {0, 1}, {1, 1}}; char dirchar[4] = {'<', '^', '>', 'v'}; // [a,b) int irand(int a, int b) { static mt19937 Rand(static_cast(time(nullptr))); uniform_int_distribution dist(a, b - 1); return dist(Rand); } // [a,b) double drand(int a, int b) { static mt19937 Rand(static_cast(time(nullptr))); uniform_real_distribution dist(a, b); return dist(Rand); } // https://qiita.com/IgnorantCoder/items/3101d6276e9bdddf872c template inline auto transform(const A &v, F &&f) { using result_type = decltype(std::declval()(std::declval())); vector y(v.size()); std::transform(std::cbegin(v), std::cend(v), std::begin(y), f); return y; } // generate vector which has multiple dimension template vector make_v(size_t size, const T &init) { return vector(size, init); } template auto make_v(size_t size, Ts... rest) { return vector(size, make_v(rest...)); } template T Max(vector a) { return *max_element(all(a)); } template T Min(vector a) { return *min_element(all(a)); } template T Sum(vector a) { return accumulate(all(a), (T)0); } // for counting using map template void Add(map &m, T item) { if (m.find(item) == m.end()) { m[item] = 1; } else { m[item]++; } } // for counting using map template void Erase(map &m, T item) { if (m.find(item) == m.end()) { } else { if (m[item] == 1) { m.erase(item); } else { m[item]--; } } } // get method for map with default value template U Get(map m, T key, U def) { if (m.find(key) == m.end()) { return def; } else { return m[key]; } } template inline bool Contains(const set &t, const T &key) { return t.find(key) != t.end(); } template inline bool Contains(const map &t, const T &key) { return t.find(key) != t.end(); } // template // struct Edge { // int from, to; // T cost; // Edge(int f, int t, T c) : from(f), to(t), cost(c) {} // }; // template // bool operator<(const Edge e1, const Edge e2) { // return e1.cost < e2.cost || (e1.cost == e2.cost && e1.from < e2.from) || // (e1.cost == e2.cost && e1.from == e2.from && e1.to < e2.to); // } // template // ostream &operator<<(ostream &os, const Edge &edge) { // os << "(" << edge.from << "->" << edge.to << ":" << edge.cost << ")"; // return os; // } // template // class Graph { // int n; // bool directed; // vector>> edges; // public: // Graph(int n, bool directed) // : n(n), directed(directed), edges(vector>>(n)) {} // void add_edge(int s, int t, T cost) { // edges[s].emplace_back(s, t, cost); // if (!directed) { // edges[t].emplace_back(t, s, cost); // } // } // Graph() {} // vector> &operator[](size_t i) { // return edges[i]; // } // int size() const { // return n; // } // }; //====================================================== ll check(ll a, ll c, int d) { // c^dまで使う int p = 1; rep(i, d) p *= c; int ans = (a / p + c - 2) / (c - 1); a %= p; while (a > 0) { if (a % c != 0) ans++; a /= c; } ans += d; return ans; } ll solve(ll a, ll b, ll c) { ll ans = INFL; ll p = 1; rep(d, 64) { chmin(ans, check(a, c, d)); p *= c; if (p > a) break; } return ans * b; } int main() { int Q; cin >> Q; rep(q, Q) { ll A, B, C; cin >> A >> B >> C; cout << solve(A, B, C) << endl; } return 0; }