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.

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

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