n,q,*t=list(map(int,open(0).read().split()))

for v,w in zip(t[::2],t[1::2]):

 if~-n:

  while v!=w:

   if v>w:v,w=w,v

   w=(w+n-2)//n

 print(v)
n,q,*t=list(map(int,open(0).read().split()))

for v,w in zip(t[::2],t[1::2]):

 while n>1and v!=w:

  if v>w:v,w=w,v

  w=(w+n-2)//n

 print(v)
n, q, *t = list(map(int, open(0).read().split()))
for v, w in zip(t[::2], t[1::2]):
    if ~-n:
        while v != w:
            if v > w:
                v, w = w, v
            w = (w + n - 2) // n
    print(v)

n, q, *t = list(map(int, open(0).read().split()))
for v, w in zip(t[::2], t[1::2]):
    while n > 1 and v != w:
        if v > w:
            v, w = w, v
        w = (w + n - 2) // n
    print(v)

-    if ~-n: -        while v != w: -            if v > w: -                v, w = w, v -            w = (w + n - 2) // n +    while n > 1 and v != w: +        if v > w: +            v, w = w, v +        w = (w + n - 2) // n