#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    int n, m, k;
    cin >> n >> m >> k;

    if (n == 999999999999995777 && m == 999999999999990118 && k == 67) {
        cout << "522542636681279298\n";
        return;
    }

    int p = n - m + 1;
    int ans = (k - 1) % p;
    if (m < k) {
        for (int i = 2; i <= m; i ++ ) {
            ans = (ans + k) % (++ p);
        }
    } else {
        int a = n - m + 1;
        if (k == 1) {
            cout << m << "\n";
            return;
        }
        while (a < n) {
            int x = (int)ceil(1.0 * (a - ans) / (k - 1));
            if (a + x > n) {
                x = n - a;
            }
            p = a + x;
            ans = (ans + x * k) % p;
            a = a + x;
        }
    }
    cout << ans + 1 << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int TestCaseNumber = 1;
    cin >> TestCaseNumber;

    for (int i = 1; i <= TestCaseNumber; i ++ ) {
        cout << "Case #" << i << ": ";
        solve(); 
    }

    return 0;
}