CF2183C.War Strategy

A war has broken out! You, as the country's top general, must strategize where to place your troops.

There are $n$ bases in a line, with the $k$-th of which being the home base for your army. Initially, there is only a single soldier at base $k$. Each day, the following happens in order:

• You give out an order by choosing a base $i$ ($1 \leq i \leq n$), and any number of soldiers inside that base (which is allowed to be $0$ or all soldiers in that base currently). Then, tell all soldiers you ordered to either move to base $i-1$ or base $i+1$. All soldiers must move in the same direction, and no soldier is allowed to move to the left of base $1$ or to the right of base $n$.
• Then, a new soldier moves onto base $k$. This soldier cannot be ordered by that day's commands.

However, time is tight, and there are only $m$ days until the enemy attacks. A base is called fortified if at least one soldier resides in it. Your job is to find the maximum number of fortified bases (including the home base) you can have by the end of the $m$-th day.

战争爆发了！作为该国的最高统帅，你必须制定部队部署策略。

有 $n$ 座基地排成一条直线，其中第 $k$ 座是你的军队的主基地。初始时，仅有 1 名士兵位于第 $k$ 座基地。每天按如下顺序发生以下事件：

• 你发布一道命令：选择一座基地 $i$（$1 \leq i \leq n$），并从中指定任意数量的士兵（可以为 $0$，也可以是该基地当前全部士兵）。然后，命令所有被选中的士兵全部向左移动至基地 $i-1$，或全部向右移动至基地 $i+1$。所有被命令的士兵必须朝同一方向移动，且不允许任何士兵移出基地 $1$ 的左侧或基地 $n$ 的右侧。
• 接着，一名新士兵进驻基地 $k$。该士兵在当天的命令中不可被选中。

然而时间紧迫，敌军将在 $m$ 天后发动进攻。若某座基地中至少有一名士兵，则称其为“已设防基地”。你的任务是：求出在第 $m$ 天结束时，所能达到的最多已设防基地数量（含主基地）。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains three integers $n$, $m$, $k$ ($1 \leq k \leq n \leq 10^5$, $1 \leq m \leq 10^9$) — denoting the number of bases, the number of days you have to fortify your bases, and the index of the home base.

It is guaranteed that the sum of $n$ across all test cases does not exceed $2\cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$m$、$k$（$1 \leq k \leq n \leq 10^5$，$1 \leq m \leq 10^9$），分别表示基地的数量、用于加固基地的天数，以及主基地的索引。

保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

For each test case, print the maximum number of bases you can fortify at the end of the $m$-th day.

对于每个测试用例，输出在第 $m$ 天结束时你能加固的基地的最大数量。

In the second test case, here is one way to fortify $3$ bases:

• On the first day, order $0$ soldiers in base $3$ to move to base $2$. At the end of the day, a new soldier moves to base $2$ (there are now $2$ soldiers in base $2$ and $0$ soldiers on any other base).
• On the second day, order $1$ soldier in base $2$ to move to base $1$. At the end of the day, a new soldier moves to base $2$. There are now $2$ soldiers in base $2$ and $1$ soldier on base $1$.
• On the third day, order $2$ soldiers in base $2$ to move to base $3$. At the end of the day, a new soldier moves to base $2$. There are now $1$ soldier in base $1$ and $2$, and $2$ soldiers in base $3$.
• There is now at least one soldier in each of bases $1$, $2$, $3$. Therefore, the answer is $3$.

In the third test case, here is one way you can achieve $3$ bases being fortified:

• On the first day, order the existing soldier to move from base $2$ to base $3$. At the end of the day, a new soldier moves to base $2$.
• On the second day, order the soldier in base $2$ to move to base $1$. At the end of the day, a new soldier moves to base $2$.
• There is now a soldier at each of bases $1,2,3$. Therefore, the answer is $3$. It can be shown we cannot have more than $3$ fortified bases by the end of day $2$.

Below is a vivid explanation of the third test case.

在第二个测试用例中，以下是一种加固 $3$ 个基地的方法：

• 第一天，在基地 $3$ 下达指令，让 $0$ 名士兵移动到基地 $2$。当天结束时，有 $1$ 名新士兵抵达基地 $2$（此时基地 $2$ 共有 $2$ 名士兵，其余所有基地的士兵数均为 $0$）。
• 第二天，在基地 $2$ 下达指令，让 $1$ 名士兵移动到基地 $1$。当天结束时，有 $1$ 名新士兵抵达基地 $2$。此时基地 $2$ 有 $2$ 名士兵，基地 $1$ 有 $1$ 名士兵。
• 第三天，在基地 $2$ 下达指令，让 $2$ 名士兵移动到基地 $3$。当天结束时，有 $1$ 名新士兵抵达基地 $2$。此时基地 $1$ 和基地 $2$ 各有 $1$ 名士兵，基地 $3$ 有 $2$ 名士兵。
• 此时，基地 $1$、$2$、$3$ 中每个基地至少有 $1$ 名士兵。因此，答案为 $3$。

在第三个测试用例中，以下是一种使 $3$ 个基地被加固的方法：

• 第一天，指令原有士兵从基地 $2$ 移动到基地 $3$。当天结束时，有 $1$ 名新士兵抵达基地 $2$。
• 第二天，指令基地 $2$ 中的士兵移动到基地 $1$。当天结束时，有 $1$ 名新士兵抵达基地 $2$。
• 此时，基地 $1$、$2$、$3$ 各有 $1$ 名士兵。因此，答案为 $3$。可以证明：到第 $2$ 天结束时，无法使超过 $3$ 个基地被加固。

以下是第三个测试用例的直观图示说明。