
//-------------------------------------------------------------
// Mebius Function
//   O( sqrt(N) )
//
// mebius(n) = 0      if n=0 mod p*p for some p
// mebius(n) = (-1)^k otherwise, where k is the number of n's prime factors
//
// properties:
//  1: mebius(nm) = mebius(n) mebius(m)   if gcd(n,m)=1
//  2: f(n) = Sigma_{d|n} g(d)
//       <=>
//     g(n) = Sigma_{d|n} f(d)mebius(n/d)
//
// Verified by
//   - CodeCraft '11 PSTR
//
// Further memoization or more might be needed.
//-------------------------------------------------------------

int mebius(int n)
{
	int f = 1;
	for(int q=2; q*q<=n; ++q)
		if( n%q == 0 )
		{
			if( n%(q*q) == 0 )
				return 0;
			n /= q;
			f *= -1;
		}
	if(n>1)
		f *= -1;
	return f;
}

