CF2257D Bermuda Rectangle

海狸正在横渡大海（没错，它确实可以做到）。这一次，它的目标是探索百慕大矩形。当然，这对海狸来说并没有危险，但从科学角度来看，这很有趣。 与百慕大三角不同，人们对百慕大矩形知之甚少。具体来说，海狸唯一可以确定的是，矩形的面积为 $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$。

对于每个查询，输出一个整数，每行一个，表示该查询对应的答案。

在第一个测试用例中，第一个查询中矩形 $(2, 3)$ 的每个格子都可以被计入答案，因为该矩形本身可以作为百慕大矩形。 第一个测试用例的第二个查询可以参考下图。答案即蓝色矩形和红色矩形相交区域的格子数。  图中有 4 个蓝色矩形，表示百慕大矩形的可能位置。红色是当前查询的矩形 $(x, y) = (4, 5)$。在第一个测试用例的第三个查询，每个能落在至少一个百慕大矩形的格子都被计入答案。 在第一个测试用例的第四个查询，查询矩形中唯一的格子可以在百慕大矩形中，因此答案为 1。 由 ChatGPT 5 翻译