G - Mod P <-> Mod Q

#pragma GCC optimize("Ofast")

#pragma GCC optimize("unroll-loops")

#pragma GCC optimize("inline")

#include<bits/stdc++.h>

using namespace std;

template<class T> struct cLtraits_identity{

  using type = T;

}

;

template<class T> using cLtraits_try_make_signed =

  typename conditional<

    is_integral<T>::value,

    make_signed<T>,

    cLtraits_identity<T>

    >::type;

template <class S, class T> struct cLtraits_common_type{

  using tS = typename cLtraits_try_make_signed<S>::type;

  using tT = typename cLtraits_try_make_signed<T>::type;

  using type = typename common_type<tS,tT>::type;

}

;

template<class S, class T> inline auto min_L(S a, T b)

-> typename cLtraits_common_type<S,T>::type{

  return (typename cLtraits_common_type<S,T>::type) a <= (typename cLtraits_common_type<S,T>::type) b ? a : b;

}

inline int my_getchar_unlocked(){

  static char buf[1048576];

  static int s = 1048576;

  static int e = 1048576;

  if(s == e && e == 1048576){

    e = fread_unlocked(buf, 1, 1048576, stdin);

    s = 0;

  }

  if(s == e){

    return EOF;

  }

  return buf[s++];

}

inline void rd(int &x){

  int k;

  int m=0;

  x=0;

  for(;;){

    k = my_getchar_unlocked();

    if(k=='-'){

      m=1;

      break;

    }

    if('0'<=k&&k<='9'){

      x=k-'0';

      break;

    }

  }

  for(;;){

    k = my_getchar_unlocked();

    if(k<'0'||k>'9'){

      break;

    }

    x=x*10+k-'0';

  }

  if(m){

    x=-x;

  }

}

inline void rd(long long &x){

  int k;

  int m=0;

  x=0;

  for(;;){

    k = my_getchar_unlocked();

    if(k=='-'){

      m=1;

      break;

    }

    if('0'<=k&&k<='9'){

      x=k-'0';

      break;

    }

  }

  for(;;){

    k = my_getchar_unlocked();

    if(k<'0'||k>'9'){

      break;

    }

    x=x*10+k-'0';

  }

  if(m){

    x=-x;

  }

}

inline int rd_int(void){

  int x;

  rd(x);

  return x;

}

struct MY_WRITER{

  char buf[1048576];

  int s;

  int e;

  MY_WRITER(){

    s = 0;

    e = 1048576;

  }

  ~MY_WRITER(){

    if(s){

      fwrite_unlocked(buf, 1, s, stdout);

    }

  }

}

;

MY_WRITER MY_WRITER_VAR;

void my_putchar_unlocked(int a){

  if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){

    fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);

    MY_WRITER_VAR.s = 0;

  }

  MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;

}

template<class T> inline void wt_L(vector<T> x);

template<class T> inline void wt_L(set<T> x);

template<class T> inline void wt_L(multiset<T> x);

template<class T1, class T2> inline void wt_L(pair<T1,T2> x);

inline void wt_L(char a){

  my_putchar_unlocked(a);

}

inline void wt_L(long long x){

  int s=0;

  int m=0;

  char f[20];

  if(x<0){

    m=1;

    x=-x;

  }

  while(x){

    f[s++]=x%10;

    x/=10;

  }

  if(!s){

    f[s++]=0;

  }

  if(m){

    my_putchar_unlocked('-');

  }

  while(s--){

    my_putchar_unlocked(f[s]+'0');

  }

}

template<class T, class U> inline T GCD_L(T a, U b){

  T r;

  while(b){

    r=a;

    a=b;

    b=r%a;

  }

  return a;

}

template<class T, class U> inline T LCM_L(T a, U b){

  return a/GCD_L(a,b)*b;

}

int main(){

  int Nzj9Y0kE;

  int bkxOPzPX = rd_int();

  for(Nzj9Y0kE=(0);Nzj9Y0kE<(bkxOPzPX);Nzj9Y0kE++){

    long long P;

    rd(P);

    long long Q;

    rd(Q);

    long long X;

    rd(X);

    long long res;

    long long c;

    if(P > Q){

      swap(P, Q);

    }

    ;

    c =LCM_L(P, Q);

    res = (X / c) * Q;

    X %= c;

    res +=min_L(X, Q);

    wt_L(res);

    wt_L('\n');

  }

  return 0;

}

template<class T> inline void wt_L(vector<T> x){

  int fg = 0;

  for(auto a : x){

    if(fg){

      my_putchar_unlocked(' ');

    }

    fg = 1;

    wt_L(a);

  }

}

template<class T> inline void wt_L(set<T> x){

  int fg = 0;

  for(auto a : x){

    if(fg){

      my_putchar_unlocked(' ');

    }

    fg = 1;

    wt_L(a);

  }

}

template<class T> inline void wt_L(multiset<T> x){

  int fg = 0;

  for(auto a : x){

    if(fg){

      my_putchar_unlocked(' ');

    }

    fg = 1;

    wt_L(a);

  }

}

template<class T1, class T2> inline void wt_L(pair<T1,T2> x){

  wt_L(x.first);

  my_putchar_unlocked(' ');

  wt_L(x.second);

}

// cLay version 20221230-1

​

// --- original code ---

// REP(rd_int()){

//   ll @P, @Q, @X, res, c;

//   sortE(P,Q);

//   c = lcm(P,Q);

//   res = (X / c) * Q;

//   X %= c;

//   res += min(X, Q);

//   wt(res);

// }