Бобр плывёт по океану (да, он и не такое может). Здесь он с целью исследовать Бермудский Прямоугольник. Бобру он, конечно, не представляет никакой опасности, но интересен с научной точки зрения.
В отличие от Бермудского Треугольника, про Бермудский Прямоугольник известно не так много. А именно, Бобр достоверно знает, что площадь прямоугольника равна $$$S$$$, его стороны целые, и левый нижний угол находится в точке $$$(0, 0)$$$.
Бобра интересует, сколько клеток из прямоугольника со сторонами $$$x$$$ и $$$y$$$, у которого левый нижний угол находится в точке $$$(0, 0)$$$, могут находиться в Бермудском Прямоугольнике. Клетка может находиться в Бермудском Прямоугольнике, если существует такой прямоугольник, который удовлетворяет заданным ограничениям Бермудского Прямоугольника и содержит в себе эту клетку. Помогите Бобру быстро отвечать на запросы! Нужно ответить на $$$q$$$ таких запросов.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10\,000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка содержит два целых числа $$$S$$$ и $$$q$$$ — площадь Бермудского Прямоугольника и количество запросов ($$$1 \le S \le 10^{14}$$$; $$$1 \le q \le 3 \cdot 10^5$$$).
Далее следуют $$$q$$$ строк, каждая из которых содержит два целых числа $$$x, y$$$ — очередной запрос ($$$1 \le x, y \le S$$$).
Гарантируется, что сумма значений $$$q$$$ по всем наборам не превосходит $$$3 \cdot 10^5$$$.
Гарантируется, что сумма значений $$$\sqrt{S}$$$ по всем наборам не превосходит $$$10^7$$$.
Для каждого запроса выведите в отдельной строке одно целое число — ответ на запрос.
36 42 34 56 61 15 22 23 48 23 15 6
61114136315
В первом наборе входных данных для первого запроса подходит любая клетка прямоугольника $$$(2, 3)$$$, так как сам этот прямоугольник может быть Бермудским.
Второй запрос первого набора изображён на рисунке. Ответ на запрос — количество клеток в пересечении синей и красной фигур.
4 синих прямоугольника — возможные расположения Бермудского прямоугольника. Красный — прямоугольник запроса $$$(x, y) = (4, 5)$$$ В третьем запросе первого набора учитывается любая клетка, которая может лежать хотя бы в одном из возможных Бермудских прямоугольников.
В четвёртом запросе первого набора единственная клетка запроса может лежать в Бермудском прямоугольнике, поэтому ответ равен $$$1$$$.
| Codeforces Round 1117 (Div. 2) |
|---|
| Закончено |
