#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define rep(i, n) for(int i = 0; i < n; i++)

int main(){
    
    // 1. 入力情報.
    LL N;
    int Q;
    scanf("%lld %d", &N, &Q);
    
    // 2. クエリ回答.
    LL v, w;
    rep(i, Q){
        scanf("%lld %lld", &v, &w);
        if(N == 1){
            printf("%lld\n", min(v, w));
        }else{
            // 2-1. v <= w に 変換.
            if(v > w) swap(v, w);
            
            // 2-2. w の 祖先 を 計算.
            set<LL> s;
            s.insert(w);
            LL q, r;
            while(w > 1){
                q = (w - 2) / N + 1;
                s.insert(q);
                w = q;
            }
            
            // 2-3. v の 祖先 を 計算.
            while(v > 1){
                if(s.count(v) > 0) break;
                q = (v - 2) / N + 1;
                v = q;
            }
            
            // 2-4. 出力.
            printf("%lld\n", v);
        }
    }
    return 0;
    
}