#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n, q; cin >> n >> q;
  while (q--) {
    int u, v; cin >> u >> v, --u, --v;
    if (n == 1) {
      cout << min(u, v) + 1 << '\n';
    } else {
      set<int> se;
      while (true) {
        se.insert(u);
        if (!u) break;
        u = (u - 1) / n;
      }
      while (true) {
        if (se.count(v)) {
          cout << v + 1 << '\n';
          break;
        }
        v = (v - 1) / n;
      }
    }
  }
}