#include <bits/stdc++.h>
using namespace std;

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

struct query {
    int r, k, i;

    bool operator < (const query& aux) const
    {
        return k < aux.k;
    }
}q[100001];

int v[200001], auxS[200001], s[200001], res[100001], auxV[200001];
int n, queries;

int main()
{
    fin >> n;

    for (int i = 1; i <= n; i++)
        fin >> v[i];

    fin >> queries;
    int bit = 0;

    for (int i = 1; i <= queries; i++)
        fin >> q[i].r >> q[i].k, q[i].i = i;
    sort(q + 1, q + queries + 1);

    for (int i = 1; i <= queries; i++)
    {
        for (; bit < q[i].k; bit++)
        {
            int sz1 = 0, sz2 = 0;

            for (int j = 1; j <= n; j++)
            {
                if (v[j] & 1)
                {
                    auxS[++sz2] = s[j] + (1 << bit);
                    auxV[sz2] = v[j] >> 1;
                }
                else
                {
                    s[++sz1] = s[j];
                    v[sz1] = v[j] >> 1;
                }
            }

            int j = 1;

            while (j <= sz2)
            {
                sz1++;
                s[sz1] = auxS[j];
                v[sz1] = auxV[j];
                j++;
            }
        }
        
        int l = 1, r = n, pos1 = -1, pos2 = -1;

        while (l <= r)
        {
            int m = (l + r) >> 1;

            if (s[m] >= q[i].r)
            {
                pos1 = m;
                r = m - 1;
            }
            else
                l = m + 1;
        }

        if (pos1 == -1 || s[pos1] != q[i].r)  
            continue;

        l = 1, r = n;

        while (l <= r)
        {
            int m = (l + r) >> 1;

            if (s[m] <= q[i].r)
            {
                pos2 = m;
                l = m + 1;
            }
            else
                r = m - 1;
        }

        res[q[i].i] = (pos2 - pos1 + 1);
    }

    for (int i = 1; i <= queries; i++)
        fout << res[i] << '\n';
  
    return 0;
}