local mfl = math.floor
local n, q = io.read("*n", "*n")
for i = 1, q do
  local v, w = io.read("*n", "*n")
  if n == 1 then
    print(math.min(v, w))
  else
    while v ~= w do
      if v < w then
        w = mfl((w + n - 2) / n)
      else
        v = mfl((v + n - 2) / n)
      end
    end
    print(v)
  end
end
