#include<stdio.h>
int n;
int f(int a,int b){
	if(a==b)return a;
	if(a<b)return f(b,a);
	if(n==1)return b;
	return f((a+n-2)/n,b);
}
int main(){
	int m,a,b;
	scanf("%d %d",&n,&m);
	while(m--){
		scanf("%d %d",&a,&b);
		printf("%d\n",f(a,b));
	}
	return 0;
}