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

int main(){
    int n,q;
    cin>>n>>q;
    long s,t,msb;
    while(q--){
        cin>>s>>t;
        for(int i=n;i>=0;i--){
            if((s^t)>>i){
                msb=1LL<<i;
                break;
            }
        }
        cout<<__builtin_popcountll(msb-s%msb)+__builtin_popcountll(t%msb)<<'\n';
    }
}