#include #include #include #include #include #include #include #include #include #include using namespace std; long long gcd(long long a, long long b){ if(b==0) return a; return gcd(b, a%b); } long long lcm(long long a, long long b){ if(a> p >> q; int n; cin >> n; if(p