#include <iostream>
#include<vector>
#define ll long long;
#define f first;
#define s second;
using namespace std;
vector<long long> niz;
vector<int> res;
long long snaga(long long n, int k) {
    if (k == 0)return 1;
    long long x = snaga(n, k / 2);
    if (k % 2 == 0) return x * x;
    return x * x * n;
}
int hormutacije(vector<long long>& niz, int n, int l, int r, int& k, int stepen) {
    if (stepen == -1) return k;
    long long maska =snaga(2, stepen);
    int x = 0;
    for (int i = l - 1; i < r; i++) {
        if ((niz[i] & maska) == maska) {
            x++;
            niz[i] = 0;
        }
    }
    if (x > k) k = x;
    if (x > n / 2) return x;
    return hormutacije(niz, n, l, r, k, stepen - 1);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        long long x;
        niz.push_back(x);
    }
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        int k = 0;
        res.push_back(hormutacije(niz, n, l, r, k, 10));
    }
    for (int i = 0; i < q; i++) {
        cout << res[i]+1 << endl;
    }
}