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

int main(){
  ll n, q;
  cin >> n >> q;
  vector<ll> ans;
  while(q--) {
    ll v, w;
    cin >> v >> w;
    v--; w--;
    if(n == 1) {
      ans.push_back(min(v,w));
      continue;
    }
    while(v != w) {
      if(v > w) swap(w,v);
      w = (w-1)/n; 
    }
    ans.push_back(w);
  }
  for(ll x : ans) cout << x+1 << endl;
  return 0;
}
