standard.cpp

#include <iostream>

/**
 * @brief Computes the minimum number of moves to reach exactly targetPosition.
 *
 * Each move advances by an integer strideLength such that:
 * - 1 <= strideLength <= maxStride
 * - strideLength is not divisible by forbiddenDivisor
 *
 * @param targetPosition The destination position x.
 * @param forbiddenDivisor The integer k; strides divisible by k are forbidden.
 * @param maxStride The integer m; maximum possible stride length.
 * @return The minimum number of moves required to reach exactly targetPosition.
 */
static long long computeMinimumMoves(long long targetPosition, long long forbiddenDivisor, long long maxStride) {
    long long maxAllowedStride = (maxStride % forbiddenDivisor == 0) ? (maxStride - 1) : maxStride;
    long long minMovesLowerBound = (targetPosition + maxAllowedStride - 1) / maxAllowedStride;

    if (minMovesLowerBound == 1) {
        return (targetPosition % forbiddenDivisor != 0) ? 1LL : 2LL;
    }

    __int128 maxReachable = static_cast<__int128>(minMovesLowerBound) * static_cast<__int128>(maxAllowedStride);
    long long slack = static_cast<long long>(maxReachable - targetPosition);

    if (forbiddenDivisor == 2) {
        return (slack % 2 == 0) ? minMovesLowerBound : (minMovesLowerBound + 1);
    }

    if (slack == 1 && (maxAllowedStride % forbiddenDivisor) == 1) {
        return minMovesLowerBound + 1;
    }

    return minMovesLowerBound;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int testCaseCount;
    std::cin >> testCaseCount;

    for (int testCaseIndex = 0; testCaseIndex < testCaseCount; ++testCaseIndex) {
        long long targetPosition;
        long long forbiddenDivisor;
        long long maxStride;
        std::cin >> targetPosition >> forbiddenDivisor >> maxStride;

        std::cout << computeMinimumMoves(targetPosition, forbiddenDivisor, maxStride) << "\n";
    }

    return 0;
}