using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _4.Problem_BinaryDigitsCount
{
    class Program
    {
        public static uint NumberOfBits(uint i)
        {
            uint numberOfBits = 0;
            while (true)
            {
                i = i / 2;
                numberOfBits++;
                if (i == 0)
                {
                    break;
                }
            }
            return numberOfBits;
        }
        static void Main()
        {
            uint mask = 0;
            bool IsNCorrect = true;
            uint B = uint.Parse(Console.ReadLine());
            uint N = uint.Parse(Console.ReadLine());
            uint[] numbers = new uint[N];
            uint[] numberOfB = new uint[N];
            for (uint i = 0; i < N; i++)
            {
                numbers[i] = uint.Parse(Console.ReadLine());
                if (numbers[i] < 1 || numbers[i] > 4000000000)
                {
                    IsNCorrect = false;
                }
            }
            if (N > 0 && N < 1001 && IsNCorrect && (B == 0 || B == 1))
            {
                for (uint i = 0; i < N; i++)
                {
                    uint numberOfbits = NumberOfBits(numbers[i]);
                    for (uint bit = 0; bit < numberOfbits; bit++)
                    {
                        if (B == 1)
                        {
                            mask = B << (int)bit;
                            if ((numbers[i] & mask) == (B << (int)bit))
                            {
                                numberOfB[i]++;
                            }
                        }
                        else //B==0
                        {
                            mask = (uint)1 << (int)bit;
                            mask = ~mask;
                            if ((numbers[i] | mask) == mask)
                            {
                                numberOfB[i]++;
                            }
                        }

                    }
                }
                for (int i = 0; i < N; i++)
                {
                    Console.WriteLine(numberOfB[i]);
                }
            }
            else
            {
                Console.WriteLine("Wrong entry!");
            }
        }
    }
}