#include <bits/stdc++.h>
using namespace std;

int64_t solve() {
	int64_t a, b, c; cin >> a >> b >> c;
	if(c == 1) return -1;
	int64_t cnt = 0;
	while(a > 0) {
		// cerr << a << endl;
		if(a < c) {
			++cnt;
			break;
		}
		if(a < 2 * c - 1) {
			cnt += 2;
			break;
		}
		if(a % c == 0) {
			++cnt;
			a /= c;
			continue;
		}
		a -= a % c;
		++cnt;
	}
	return cnt * b;
}

int main() {
	int q; cin >> q;
	while(q--) {
		cout << solve() << '\n';
	}
	return 0;
}