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

int n, q, vv, w;
set<int> get(int v)
{
    set<int> a;
    while (v and a.find(v) == a.end()) {
        a.insert(v);
        v = (v + n - 2) / n;
    }
    return a;
}
void solve()
{
    if (n == 1) {
        cout << min(vv, w) << endl;
        return;
    }
    auto s = get(vv);
    auto t = get(w);
    int ans = 1;
    for (auto ss : s) {
        if (t.find(ss) != t.end())
            ans = ss;
    }
    cout << ans << endl;
}
int main()
{
    n = 3;
    get(12);
    cin >> n >> q;
    rep(i, q) cin >> vv >> w, solve();
}
