#include <iostream>
#include <string>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <tuple>
#include <queue>
#include <set>
#include <math.h>
#include <array>
#include <list>
#include <set>
#define MOD 1000000007
#define INF 1000000000
using namespace std;
typedef long long ll;
typedef tuple<ll,int,int> p;
typedef vector<int> vi;
set <int> st;
vector<int> videos(105);
double now=0;
queue<int> num;
ll n,q;
vi v(100005);
vi w(100005);
int main(int argc,char const* argv[])
{
  cin >> n >> q;
  for(int i=0;i<q;i++)
    {
      cin >> v[i] >> w[i];
    }
  for(int i=0;i<q;i++)
    {
      if(n==1)
	{
	  cout << min(v[i],w[i]) << endl;
	}
      else
	{
	  while(v[i]!=w[i])
	    {
	      if(v[i]>w[i])
		{
		  v[i]=(v[i]+n-2)/n;
		}
	      else
		{
		  w[i]=(w[i]+n-2)/n;
		}
	    }
	  cout << v[i] << endl;
	}
    }
  return 0;
}
