using System;

class BinaryDigit
{
    static void Main()
    {
        byte BinaryDigit = byte.Parse(Console.ReadLine());
        int n = int.Parse(Console.ReadLine());
        int count = 0;
        for (int i = 0; i < n; i++)
        {
            long chech = long.Parse(Console.ReadLine());
            string binari = Convert.ToString(chech, 2);
            for (int j = 0; j < binari.Length; j++)
            {
                if (byte.Parse(binari[j].ToString())==BinaryDigit)
                {
                    count++;
                }
            }
            Console.WriteLine(count);
            count = 0;
        }

    }
}