#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<set>
#define sqr(x) (x)*(x)
using namespace std;
int n,m,i,j,q,x,y;
int main()
{
	ios::sync_with_stdio(0);
	cin>>n>>q;
	while (q--)
	{
		cin>>x>>y;
		if (n==1)
		{
			cout<<min(x,y)<<endl;
			continue;
		}
		set<int> s;
		while (x!=0)
		{
			s.insert(x);
			if (x%n>1) x+=n-(x%n);
			x/=n;
		}
		x=y;
		while (x!=0)
		{
			if (s.count(x)) break; 
			if (x%n>1) x+=n-(x%n);
			x/=n;
		}
		cout<<x<<endl;
	}
	return 0;
}