#include <bits/stdc++.h>
using namespace std;

#define REP(i, m, n) for (int i = (m); i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define reps(i, n) for (int i = 0; i <= (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
typedef long long ll;
const ll INF = 1LL << 60;
const ll mod = 1e9 + 7;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N, Q; cin >> N >> Q;
    int v, w;
    if (N == 1) {
        rep(i, Q) {
            cin >> v >> w;
            cout << v << '\n';
        }
        return 0;
    }
    rep(i, Q) {
        cin >> v >> w;
        while (v != w) {
            if (v > w) v = (v + N - 2) / N;
            else w = (w + N - 2) / N;
        }
        cout << v << '\n';
    }
    return 0;
}