local mfl = math.floor
local n, q = io.read("*n", "*n")
for i = 1, q do
  local v, w = io.read("*n", "*n")
  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
