百慕大矩形AI (CI翻译)
The Beaver is swimming across the ocean (yes, he can do that). Here, it aims to explore the Bermuda Rectangle. Of course, it poses no danger to The Beaver, but it is interesting from a scientific perspective.
海狸正在横渡海洋（没错，它确实能做到）。在这里，它的目标是探索百慕大矩形。当然，这对海狸来说没有任何危险，但从科学角度来看很有趣。AI (CI翻译)
Unlike the Bermuda Triangle, not much is known about the Bermuda Rectangle. Specifically, The Beaver knows for sure that the area of the rectangle is $S$, its sides are integers, and the bottom left corner is located at the point $(0, 0)$.
与百慕大三角不同，人们对百慕大矩形知之甚少。具体来说，海狸可以确定，矩形的面积为 $S$，其边长为整数，且左下角位于点 $(0, 0)$。AI (CI翻译)
The Beaver is interested in how many cells from a rectangle with sides $x$ and $y$, whose bottom left corner is at the point $(0, 0)$, can be located within the Bermuda Rectangle. A cell is considered to be within the Bermuda Rectangle if there exists a rectangle that satisfies the given constraints of the Bermuda Rectangle and contains that cell. Help The Beaver quickly respond to queries! You need to answer $q$ such queries.
海狸想知道，在一个边长为 $x$ 和 $y$、左下角位于点 $(0, 0)$ 的矩形中，有多少个格子可能位于百慕大矩形内。如果存在一个满足百慕大矩形给定条件且包含该格子的矩形，则认为这个格子位于百慕大矩形内。请帮助海狸快速回答查询！你需要回答 $q$ 个查询。AI (CI翻译)
Input
输入格式
AI (CI翻译)Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10\,000$). The description of the test cases follows.
每个测试文件包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10\,000$）。接下来是各测试用例的描述。AI (CI翻译)
The first line of each test case contains two integers $S$ and $q$ — the area of the Bermuda Rectangle and the number of queries ($1 \le S \le 10^{14}$; $1 \le q \le 3 \cdot 10^5$).
每个测试用例的第一行包含两个整数 $S$ 和 $q$——百慕大矩形的面积以及查询数量（$1 \le S \le 10^{14}$；$1 \le q \le 3 \cdot 10^5$）。AI (CI翻译)
This is followed by $q$ lines, each containing two integers $x, y$ — the next query ($1 \le x, y \le S$).
接下来 $q$ 行，每行包含两个整数 $x, y$——一个查询（$1 \le x, y \le S$）。AI (CI翻译)
It's guaranteed that the sum of $q$ over all test cases doesn't exceed $3 \cdot 10^5$.
保证所有测试用例中 $q$ 的总和不超过 $3 \cdot 10^5$。AI (CI翻译)
It's guaranteed that the sum of $\sqrt{S}$ over all test cases doesn't exceed $10^7$.
保证所有测试用例中 $\sqrt{S}$ 的总和不超过 $10^7$。AI (CI翻译)
Output
输出格式
AI (CI翻译)For each query, output a single integer on a separate line — the answer to the query.
对于每个查询，在单独的一行中输出一个整数——该查询的答案。AI (CI翻译)
Note
说明
AI (CI翻译)In the first test case, every cell of the rectangle $(2, 3)$ is counted in the first query, since this rectangle itself can be the Bermuda Rectangle.
在第一个测试用例中，第一个查询中的矩形 (2, 3) 的每个格子都会被计数，因为该矩形本身就可以作为百慕大矩形。AI (CI翻译)
The second query of the first test case is illustrated in the figure. The answer to the query is the number of cells in the intersection of the blue and red shapes.
第一个测试用例的第二个查询如图所示。该查询的答案是蓝色图形和红色图形交集中的格子数量。AI (CI翻译)
4 blue rectangles — possible positions of the Bermuda Rectangle. Red — the rectangle of the query $(x, y) = (4, 5)$
4 个蓝色矩形——百慕大矩形的可能位置。红色——查询矩形 (x, y) = (4, 5)AI (CI翻译)
In the third query of the first test case, every cell that can lie in at least one possible Bermuda Rectangle is counted.
在第一个测试用例的第三个查询中，所有可能位于至少一个百慕大矩形内的格子都会被计数。AI (CI翻译)
In the fourth query of the first test case, the only cell of the query rectangle can lie in the Bermuda Rectangle, so the answer is $1$.
在第一个测试用例的第四个查询中，查询矩形中唯一的格子可以位于百慕大矩形内，因此答案为 $1$。AI (CI翻译)
样例
3
6 4
2 3
4 5
6 6
1 1
5 2
2 2
3 4
8 2
3 1
5 6
6
11
14
1
3
6
3
15
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。