using System;
using System.Collections.Generic;
using System.Text;
using System.Reflection;
public static class Utility
{
public static int Count1Bit(ulong n)
{
int count = 0;
while (n != 0)
{
count++;
n &= (n - 1);
}
return count;
}
}