当前没有测试数据。

题目描述

海狸正在横渡大洋（没错，它可以做到）。它打算探索百慕大矩形。当然，它对海狸没有危险，但有着很高的科研研究价值。

和百慕大三角不同，人类对百慕大矩形知之甚少。目前海狸只确定：该矩形的面积为 $S$，边长均为整数，且它的左下角位于坐标点 $(0,0)$。

海狸想知道：对于一个左下角在 $(0,0)$、边长为 $x$ 和 $y$ 的矩形，其中有多少个格子有可能落在百慕大矩形内部。 一个格子被算作落在百慕大矩形内的条件是：存在一个满足上述全部约束的百慕大矩形，能够包含这个格子。请帮助海狸处理一共 $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$。

输出格式

对每次询问，单独输出一行一个整数，表示该次询问的答案。

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

说明

第一组测试用例的第一个询问，询问矩形 $(2,3)$ 的全部格子都会被统计，因为该矩形本身就可以作为百慕大矩形。

第一组测试用例的第二个询问对应配图，答案为蓝色图形与红色图形相交部分的格子数量。 图中 4 个蓝色矩形代表百慕大矩形所有可能的形态；红色代表本次询问 $(x,y)=(4,5)$ 的查询矩形。

第一组测试用例第三个询问，统计所有至少能被某一个合法百慕大矩形覆盖到的格子。

第一组测试用例第四个询问，查询矩形仅有的那一个格子可以被百慕大矩形包含，答案为 $1$。

原题链接

原题链接