N, Q = map(int, input().split())
query = [list(map(int, input().split())) for _ in range(Q)]
ans = []
for s, t in query:
    for i in range(N-1, -1, -1):
        m = ((s-1)//(1 << i)+1)*(1 << i)
        if t >= m:
            break
    ans.append(str(bin(s-m)).count('1')+str(bin(t-m)).count('1'))

print(*ans, sep='\n')