#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,q,l,r,i,j,k,t;
    cin >> n >> q;
    vector<int> a(n);
    map<int,int> prob;
    vector<pair<int,int>> p;
    for(i = 0; i < n; i++)
        cin >> a[i];
    for(t = 0; t < q; t++){
        cin >> l >> r;
        l--;
        r--;
        p.clear();
        prob.clear();
        for(i = l; i <= r; i++)
            for(j = i+1; j <= r; j++)
                if((a[i]&a[j]) <= (a[i]^a[j])){
                    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[i] = p.back();
                    p.pop_back();
                }
                else i++;
            }
            removed++;
        }
        cout << ((r-l)+1)-removed << "\n";
    }
    return 0;
}