#include <iostream>
#include <fstream>
#include <vector>

std::ifstream fin("rk.in");
std::ofstream fout("rk.out");

unsigned long long n, q, r, k, a[200001];
bool numere[2000000001];

void citire()
{
    fin>>n;
    int x, maxNR = 0;
    for(int i = 0; i < n; i++)
    {
        fin>>x;
        a[i] = x;
//        numere[x] = true;
        if(maxNR < x)
        {
            maxNR = x;
        }
//        fin>>a[i];
    }
    for(int i = 0; i <= maxNR; i++)
    {
        numere[i] = false;
    }
    for(int i = 0; i < n; i++)
    {
        numere[a[i]] = true;
    }

    fin>>q;
    for(int i = 0; i < q; i++)
    {
        fin>>r>>k;
        unsigned long long nr = 0;
        unsigned long long putere = 1<<k;

        for(int j = r; j <= maxNR; j+=putere)
        {
            if(numere[j])
            {
                nr++;
            }
        }

//        for(int j = 0; j < n; j++)
//        {
//            if(a[j] % (1<<k) == r)
//            {
//                nr++;
//            }
//        }
        fout<<nr<<'\n';
    }
}

int main()
{
    citire();
    return 0;
}