#include <iostream>
#include <cstdio>
using namespace std;

int gcd(int a, int b){

int p,q,r;

if(a<b){p=b;b=a;a=p;

}

   while(r!=0){
   q=b/a;
   r=b%a;
   b=a;
   a=r;
   }
   return b;
}

int main(void)
{    int a, b;
     while((r=b%a)!=0){
  q=b/a;
  b=a;
  a=r;
  }
  return a;
}
