#include using namespace std; typedef signed long long ll; #define _P(...) (void)printf(__VA_ARGS__) #define FOR(x,to) for(x=0;x<(to);x++) #define FORR(x,arr) for(auto& x:arr) #define FORR2(x,y,arr) for(auto& [x,y]:arr) #define ALL(a) (a.begin()),(a.end()) #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) template bool chmax(T &a, const T &b) { if(a bool chmin(T &a, const T &b) { if(a>b){a=b;return 1;}return 0;} //------------------------------------------------------- int T; ll P1,Q1,P2,Q2; const int prime_max = 32000; vector prime; int NP,divp[prime_max]; void cprime() { if(NP) return; for(int i=2;i=i&&j>T; while(T--) { cin>>P1>>Q1>>P2>>Q2; while(P1!=P2||Q1!=Q2) { if(Q1-P1P2) swap(P1,P2),swap(Q1,Q2); //cout<