#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    ll n, q; cin >> n >> q;
    vector<ll>a(n);
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    
    ll l, r, res1, res2, res = 0;
    for (int k = 0; k < q; k++){
        cin >> l >> r; l--;
        res = 0;
        for (int i = l; i < r; i++){
            for ( int j = l; j < r; j++){
                res1 = a[i] ^ a[j];
                res2 = a[i] & a[j];
                if (res1 < res2){
                    res++;
                }
            }
        }
        cout << (ll)sqrt(res) << '\n';
    }
    
    return 0;
}