// #define _GLIBCXX_DEBUG #include using namespace std; using uint = unsigned int; using ll = long long; #define CIN( LL , A ) LL A; cin >> A #define GETLINE( A ) string A; getline( cin , A ) #define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR ) #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) #define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( ll VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) #define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ ) #define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES ) #define QUIT return 0 #define RETURN( ANSWER ) cout << ( ANSWER ) << "\n"; QUIT #define DOUBLE( PRECISION , ANSWER ) cout << fixed << setprecision( PRECISION ) << ( ANSWER ) << "\n"; QUIT #define MIN( A , B ) A < B ? A : B; #define MAX( A , B ) A < B ? B : A; template inline T Absolute( const T& a ){ return a > 0 ? a : - a; } // 以下、自分のライブラリ(https://github.com/p-adic/cpp)よりソースコードをコピーして編集している。 template inline INT GCD( const INT& a , const INT& b ) { INT a_c = a >= 0 ? a : -a; INT b_c = b >= 0 ? b : -b; while( a_c > 0 && b_c > 0 ){ if( a_c < b_c ){ b_c -= a_c * ( b_c / a_c ); } else { a_c -= b_c * ( a_c / b_c ); } } return a_c > 0 ? a_c : b_c; } template inline INT FloorSum( const INT& a_0 , const INT& a_1 , const INT& q , const INT& n ) { if( n == 0 ){ return 0; } else if( n == 1 ){ return a_0 / q; } const INT r_0 = a_0 % q; const INT r_1 = a_1 % q; const INT value_lim = ( r_0 + r_1 * n ) / q; INT answer = ( a_0 / q ) * n + ( a_1 / q ) * ( n % 2 == 0 ? ( n / 2 ) * ( n - 1 ) : n * ( ( n - 1 ) / 2 ) ); if( value_lim != 0 ){ const INT r_1_n_approx = value_lim * q - r_0; const INT e = r_1_n_approx % r_1; // r_1 == 0と仮定するとvalue_lim == r_0 / qすなわちvalue_lim == 0となり矛盾する。 answer += ( n - ( ( r_1_n_approx + ( r_1 - 1 ) ) / r_1 ) ) * value_lim + FloorSum( e == 0 ? 0 : r_1 - e , q , r_1 , value_lim ); } return answer; } int main() { UNTIE; CIN( ll , T ); ll P , Q , K; ll gcd; constexpr const ll power_max = ll( 1 ) << 31; REPEAT( T ){ cin >> P >> Q >> K; assert( P > 0 && Q > 0 && K > 0 ); gcd = GCD( P , Q ); P /= gcd; Q /= gcd; ll K_border = ( ( P - 1 ) * ( Q - 1 ) ) / 2; ll answer; if( K > K_border ){ answer = K + K_border; } else { if( P < Q ){ swap( P , Q ); } ll r = P / Q; if( K <= r ){ answer = K * Q; } else { ll K_a; ll x_a = 0; ll power = power_max; ll x_a_p = 0; ll difference; while( power != 0 ){ x_a_p = x_a + power; K_a = ( P * ( x_a_p * ( x_a_p + 1 ) ) / 2 ) / Q + x_a_p - 1; difference = K - K_a; if( difference >= 0 ){ x_a = x_a_p; if( difference == 0 ){ break; } } power /= 2; } assert( x_a > 0 ); answer = ( Q * ( K - x_a + 1 ) - P * ( ( x_a * ( x_a + 1 ) ) / 2 ) ) / x_a; if( answer < 1 ){ answer = 1; } ll n = answer / P + 1; ll floor_sum = FloorSum( answer % P , P , Q , n ) + n - 1; ll answer_c = answer; power = 1; bool match = false; if( K > floor_sum ){ answer_c = answer + power; n = answer_c / P + 1; ll floor_sum_prev = floor_sum; floor_sum = FloorSum( answer_c % P , P , Q , n ) + n - 1; while( K > floor_sum ){ power *= 2; answer_c = answer + power; n = answer_c / P + 1; floor_sum_prev = floor_sum; floor_sum = FloorSum( answer_c % P , P , Q , n ) + n - 1; } if( K != floor_sum ){ power /= 2; floor_sum = floor_sum_prev; } } else { if( K == floor_sum ){ answer_c = answer - power; n = answer_c / P + 1; if( K != FloorSum( answer_c % P , P , Q , n ) + n - 1 ){ match = true; power /= 2; answer = answer_c + 1; break; } } while( true ){ power *= 2; answer_c = answer - power; if( answer_c <= 0 ){ answer_c = 1; n = answer_c / P + 1; floor_sum = FloorSum( answer_c % P , P , Q , n ) + n - 1; break; } n = answer_c / P + 1; floor_sum = FloorSum( answer_c % P , P , Q , n ) + n - 1; if( K > floor_sum ){ power /= 2; answer = answer_c; break; } else if( K == floor_sum ){ answer_c--; n = answer_c / P + 1; if( K != FloorSum( answer_c % P , P , Q , n ) + n - 1 ){ match = true; power /= 2; answer = answer_c + 1; break; } } } } if( ! match ){ while( true ){ assert( power != 0 ); answer_c = answer + power; n = answer_c / P + 1; floor_sum = FloorSum( answer_c % P , P , Q , n ) + n - 1; if( K > floor_sum ){ answer = answer_c; } else if( K == floor_sum ){ if( answer_c == 1 || power == 1 ){ answer = answer_c; break; } else { answer_c--; n = answer_c / P + 1; if( K > FloorSum( answer_c % P , P , Q , n ) + n - 1 ){ answer = answer_c + 1; break; } } } power /= 2; } } } } answer *= gcd; cout << answer << "\n"; } return 0; }