#define _USE_MATH_DEFINES #include #include #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; int main() { int q; cin >> q; while(--q >= 0){ int a, b, c; cin >> a >> b >> c; if(c == 1){ cout << -1 << endl; continue; } set s; queue q; s.insert(a); q.push(a); long long ans = 0; while(*s.begin() != 0){ ans += b; int n = q.size(); while(--n >= 0){ int x = q.front(); q.pop(); vector v = {x / c * c}; if(x % c == 0) v.push_back(x / c); if(c - 1 <= x) v.push_back(x - (c - 1)); for(int y : v){ if(s.find(y) == s.end()){ s.insert(y); q.push(y); } } } } cout << ans << endl; } return 0; }