int bitcnt(LL x)
{
	int c = 0;
	for(; x; x>>=1)
		c += x&1;
	return c;
}
