#include <bits/stdc++.h>
using namespace std;
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int n,q,l,r;
    cin >> n >> q;
    vector<int> a(n);
    vector<pair<int,int>> p;
    for(int i = 0; i < n; i++)
        cin >> a[i];

    for(int i = 0; i < n; i++)
    {
        for(int j = i; j < n; j++)
        {
            if((a[i]&a[j]) < (a[i]^a[j]))
            {
                p.push_back({min(i,j),max(i,j)});
            }
        }
    }
    for(int t = 0; t < q; t++)
    {
        cin >> l >> r;
        l--;
        r--;
        if(r-l == 1)
        {
            cout << "1\n";
            continue;
        }
        map<int,int> gg;
        for(int i = 0; i < p.size(); i++)
        {
            gg[p[i].first]++;
            gg[p[i].second]++;
        }
        vector<int> g;
        int sum = 0;
        for(const auto& temp:gg)
        {
            //first = val, second = num
            g.push_back(temp.second);
            sum+=temp.second;
        }
        if(g.size() == 0)
        {
            cout << (r-l) << "\n";
            continue;
        }
        sort(g.begin(),g.end());
        reverse(g.begin(),g.end());
        int sakup = 0;
        for(int i = 0; i < g.size(); i++)
        {
            sakup+=g[i];
            if(sakup*2 == sum)
            {
                cout << r-l-i << "\n";
                break;
            }
        }
    }
    return 0;
}