ll@T;rep(T){ll@A,@B,@K,C=A,D=B,L=0,R=1LL<<62,M;if(A>B)swap(C,D);while(C)D%=C,swap(C,D);C=A*B/D;while(L+1<R){M=(L+1+R)/2;(M-M/A-M/B+M/C<K?L:R)=M;}wt(R);}