CF2257D.Bermuda Rectangle

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.

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)$.

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.

海狸正在横渡海洋（是的，它能做到）。在此过程中，它旨在探索“百慕大矩形”。当然，这对海狸毫无危险，但从科学角度看却十分有趣。

与“百慕大三角”不同，人们对“百慕大矩形”知之甚少。具体而言，海狸确知该矩形的面积为 $S$，其边长均为整数，且左下角位于点 $(0, 0)$。

海狸感兴趣的问题是：对于一个左下角位于点 $(0, 0)$、边长分别为 $x$ 和 $y$ 的矩形，其中最多有多少个单位格子能被包含在某个满足上述“百慕大矩形”约束条件（即面积为 $S$、边长为整数、左下角在 $(0, 0)$）的矩形内？若存在某个满足约束的“百慕大矩形”包含该单位格子，则称该格子位于“百慕大矩形”内。请帮助海狸快速回答此类查询！你需要回答 $q$ 个这样的查询。

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.

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$).

This is followed by $q$ lines, each containing two integers $x, y$ — the next query ($1 \le x, y \le S$).

It's guaranteed that the sum of $q$ over all test cases doesn't exceed $3 \cdot 10^5$.

It's guaranteed that the sum of $\sqrt{S}$ over all test cases doesn't exceed $10^7$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each query, output a single integer on a separate line — the answer to the query.

对于每个查询，在单独的一行上输出一个整数——该查询的答案。

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.

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.

4 blue rectangles — possible positions of the Bermuda Rectangle. Red — the rectangle of the query $(x, y) = (4, 5)$

In the third query of the first test case, every cell that can lie in at least one possible Bermuda Rectangle is counted.

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$.

在第一个测试用例中，矩形 $(2, 3)$ 的每个单元格都在第一次查询中被计入，因为该矩形本身即可作为百慕大矩形。

第一个测试用例的第二次查询如图所示。该查询的答案为蓝色与红色图形交集区域内的单元格数量。

4 个蓝色矩形——百慕大矩形的可能位置；红色——查询矩形 $(x, y) = (4, 5)$

在第一个测试用例的第三次查询中，所有至少能属于某一个可能的百慕大矩形的单元格均被计入。

在第一个测试用例的第四次查询中，查询矩形中唯一的一个单元格可以属于百慕大矩形，因此答案为 $1$。