#include<bits/stdc++.h>
using namespace std;
#define ll long long;
ll gcd(ll a,ll b){
  if(a<b) swap(a,b);
  ll c;
  c=a%b;
  a=b;
  b=c;
  if(b!=0)
    a=gcd(a,b);
  return a;
}
ll lcm(ll a,ll b){
  return a*b/gcd(a,b);
}
int main(){
  