#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair < int , int > pii ;
typedef vector < int > vi ;
#define fi first
#define se second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

int test_id ;

void solve ( ) {
    ll n , m , k ;
    cin >> n >> m >> k ;
    ++ test_id ;
    cout << "Case #" << test_id << ": " ;
    if ( k == 1 ) {
        cout << m << "\n" ;
        return ;
    }
    if ( k <= m ) {
        ll taken = 0 , rem = n ;
        ll x = k ;
        vector < ll > v ;
        ll ans = -1 ;
        while ( 1 ) {
            ll tot = 1 + ( rem - x ) / k ;
            if ( taken + tot >= m ) {
                ans = x + ( m - taken - 1 ) * k ;
                if ( ans > rem ) { ans -= rem ; }
                break ;
            }
            else {
                v.push_back ( x ) ;
                x += tot * k ;
                x %= rem ;
                if ( x == 0 ) { x += k ; }
                taken += tot , rem -= tot ;
            }
        }
        reverse ( v.begin ( ) , v.end ( ) ) ;
        for ( auto st : v ) {
            if ( st <= ans ) {
                ll coef = 1 + ( ans - st ) / ( k - 1 ) ;
                ans += coef ;
            }

        }
        cout << ans << "\n" ;
    }
    else {
        ll ans = 0 ;
        for ( ll i = n - m + 1 ; i <= n ; ++ i ) {
            ll pos = k % i ;
            if ( pos == 0 ) { pos = i ; }
            ans = ans + pos ;
            if ( ans > i ) { ans -= i ; }
        }
        cout << ans << "\n" ;
    }
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; cin >> t ;
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}