#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,q,l,r;
    cin >> n >> q;
    vector<int> a(n);
    map<int,int> prob;
    vector<pair<int,int>> p;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    for(int t = 0; t < q; t++)
    {
        cin >> l >> r;
        l--;
        r--;
        for(int i = l; i <= r; i++)
        {
            for(int j = i+1; j <= r; j++)
            {
                if((a[i]&a[r]) <= (a[i]^a[r]))
                {
                    p.push_back({i,j});
                    prob[i]++;
                    prob[j]++;
                }
            }
        }
        int removed = 0;
        int maksamount = 0;
        int makspos = 0;
        while(p.size() != 0)
        {
            maksamount = 0;
            makspos = 0;

            for(const auto& g:prob){
                if(g.second > maksamount){
                    maksamount = g.second;
                    makspos = g.first;
                }
            }
            for(int i = 0; i < p.size();){
                if(p[i].first == makspos || p[i].second == makspos){
                    prob[p[i].first]--;
                    prob[p[i].second]--;
                    p.erase(p.begin()+i);
                }
                else i++;
            }
            removed++;
        }
        cout << ((r-l)+1)-removed << "\n";
    }
    return 0;
}