#include #include #include #include using namespace std; int solve(int x, int y, int a) { vector> fromX; for (int i = 0; i < 100; i++) { fromX.emplace_back(x, i); x /= a; } // from[i] = {floor(y / a^i), y to floor(y / a^i), y to floor(y / a^i) + 1} vector> fromY; fromY.emplace_back(y, 0, 1e9); while (1) { auto [i, j, k] = fromY.back(); int d = i / a, r = i % a; if (r == 0) { fromY.emplace_back(d, min(j + 1, k + 2), k + a); } else if (r == a - 1) { fromY.emplace_back(d, j + a, min(j + 2, k + 1)); } else { fromY.emplace_back( d, min(j + r + 1, k + r + 2), min(j + a - r + 1, k + a - r)); } if (i == 0) break; } int ans = 1e9; for (auto &i : fromX) { for (auto &j : fromY) { ans = min({ans, abs(get<0>(j) - get<0>(i)) + get<1>(j) + get<1>(i), abs(get<0>(j) + 1 - get<0>(i)) + get<2>(j) + get<1>(i)}); } } return ans; } int main() { ios::sync_with_stdio(false); std::cin.tie(nullptr); int t; cin >> t; for(int i = 0; i < t; i++) { int x, y, a; cin >> x >> y >> a; cout << solve(x, y, a) << '\n'; } }