#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
typedef long long ll;
typedef pair<ll,ll> p;
template<class t> inline bool chmax(t& a, t b) { if (a < b) { a = b; return 1; } return 0; }
template<class t> inline bool chmin(t& a, t b) { if (a > b) { a = b; return 1; } return 0; }
const ll mod=1000000007;
const ll linf=1ll<<60;
const int inf=1<<30;
int dx[]={1,0,-1,0,1,-1,1,-1};
int dy[]={0,1,0,-1,1,-1,-1,1};



int main(){
    int n,q;cin >> n >> q;
    for (int i = 0; i < q; i++) {
        int v,w;cin >> v >> w;
        if(n==1){
            cout << min(v,w) << endl;
            continue;
        }
        set<int> st;
        while(v){
            st.insert(v);
            v = (v + n - 2) / n;
        }
        while(w){
            if(st.find(w) != st.end()){
                cout << w << endl;
                break;
            }
            w = (w + n - 2) / n;
        }
    }
    return 0;
}
