#include<bits/stdc++.h>
#define ll long long int
#define vec vector<ll>
#define f(var,a,b) for(ll var = a ; var < b ; var++ )
#define fr(var,a,b) for(ll var = a ; var > b ; var-- )
#define fasthoja ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
ll chefItUp(ll n) {
// unset_bits keeps track of count of un-set
// bits in binary representation of n
ll unset_bits=0;
while (n) {
if ((n & 1) == 0)
unset_bits++;
n=n>>1;
}
return 1 << unset_bits;
}
int main(void) {
fasthoja;
ll t; cin>>t;
while(t--) {
ll n; cin >> n;
vec cip;
f(i,1,n+1) {
cip.push_back( chefItUp(i) );
}
vec psum( cip.size() );
psum[0] = cip[0];
f( i,1,cip.size() ) {
psum[i] = psum[i-1] + cip[i];
}
ll q; cin >> q;
f(i,0,q) {
ll l,r; cin >> l >> r;
if( l == 1 ) cout << psum[r-1] << "\n";
else {
cout << psum[r-1] - psum[l-2] << "\n";
}
}
}//end of test case loop
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBsbCBsb25nIGxvbmcgaW50CiNkZWZpbmUgdmVjIHZlY3RvcjxsbD4KI2RlZmluZSBmKHZhcixhLGIpIGZvcihsbCB2YXIgPSBhIDsgdmFyIDwgYiA7IHZhcisrICkKI2RlZmluZSBmcih2YXIsYSxiKSBmb3IobGwgdmFyID0gYSA7IHZhciA+IGIgOyB2YXItLSApCiNkZWZpbmUgZmFzdGhvamEgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7IGNpbi50aWUoTlVMTCk7Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKbGwgY2hlZkl0VXAobGwgbikgewoJLy8gdW5zZXRfYml0cyBrZWVwcyB0cmFjayBvZiBjb3VudCBvZiB1bi1zZXQKCS8vIGJpdHMgaW4gYmluYXJ5IHJlcHJlc2VudGF0aW9uIG9mIG4KCWxsIHVuc2V0X2JpdHM9MDsKCXdoaWxlIChuKSB7CgkJaWYgKChuICYgMSkgPT0gMCkKCQkJdW5zZXRfYml0cysrOwoJCW49bj4+MTsKCX0KCglyZXR1cm4gMSA8PCB1bnNldF9iaXRzOwp9CgppbnQgbWFpbih2b2lkKSB7CgogICAgZmFzdGhvamE7CiAgICBsbCB0OyBjaW4+PnQ7CiAgICB3aGlsZSh0LS0pIHsKICAgICAgICBsbCBuOyBjaW4gPj4gbjsKCiAgICAgICAgdmVjIGNpcDsKCiAgICAgICAgZihpLDEsbisxKSB7CiAgICAgICAgICAgIGNpcC5wdXNoX2JhY2soIGNoZWZJdFVwKGkpICk7CiAgICAgICAgfQoKICAgICAgICB2ZWMgcHN1bSggY2lwLnNpemUoKSApOwoKICAgICAgICBwc3VtWzBdID0gY2lwWzBdOwogICAgICAgCiAgICAgICAgZiggaSwxLGNpcC5zaXplKCkgKSB7CiAgICAgICAgICAgIHBzdW1baV0gPSBwc3VtW2ktMV0gKyBjaXBbaV07CiAgICAgICAgICAgCiAgICAgICAgfQogICAgICAgIAogICAgICAgIAogICAgICAgIGxsIHE7IGNpbiA+PiBxOwogICAgICAgIGYoaSwwLHEpIHsKICAgICAgICAgICAgbGwgbCxyOyBjaW4gPj4gbCA+PiByOwogICAgICAgCiAgICAgICAgICAgIGlmKCBsID09IDEgKSBjb3V0IDw8IHBzdW1bci0xXSA8PCAiXG4iOwogICAgICAgICAgICBlbHNlIHsKICAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgICBjb3V0IDw8IHBzdW1bci0xXSAtIHBzdW1bbC0yXSA8PCAiXG4iOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIAogICAgfS8vZW5kIG9mIHRlc3QgY2FzZSBsb29wCgogICAgCiAgICByZXR1cm4gMDsKfQ==