Make It Special

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

#define ll     long long
#define _test   int _TEST; cin>>_TEST; while(_TEST--)
#define pb     push_back

int main()
{
    _test
    {
        ll int n, q;
        cin>>n>>q;

        int maxBit = 0;

        for(int b=0; b<61; b++)
        {
            if((n & (1ll<<b)) != 0)
                maxBit = b;
        }

        ll int pow2 = (1ll << (maxBit+1));

        while(q--)
        {
            ll int l, r;
            cin>>l>>r;

            ll int rr = r / pow2;
            ll int tmpl = (l-1) / pow2;

            ll int ans = (rr - tmpl);

            rr = (r+1) / pow2;
            tmpl = (l) / pow2;

            ans += (rr - tmpl);

            cout << max(0ll, ans) << "\n";
        }
    }
}