static int gcd(int a, int b)
{
	while (b != 0) 
	{
		int tmp = a % b;
		a = b;
		b = tmp;
	}
	return a;
}

static int lcm(int a, int b)
{
	return a / gcd(a, b) * b;
}