战争爆发了!作为国家最高将领,你必须制定军队部署的战略。
一条线上有 $$$n$$$ 个基地,其中第 $$$k$$$ 是你军队的大本营。最初,基地只有一名士兵$$$k$$$。每天,都会按顺序发生以下事情:
- 您通过选择基础 $$$i$$$ ($$$1 \leq i \leq n$$$) 发出订单,并且 任何 该基地内的士兵数量(允许为 $$$0$$$ 或当前该基地内的所有士兵)。然后,告诉所有你命令的士兵要么转移到基地 $$$i-1$$$ 要么转移到基地 $$$i+1$$$。所有士兵必须朝同一方向移动,并且不允许任何士兵移动到基地$$$1$$$的左侧或基地$$$n$$$的右侧。
- 然后,一名新士兵移动到基地$$$k$$$。这位士兵不能按照当天的命令来指挥。
然而,时间紧迫,距离敌人进攻只有$$$m$$$天了。一个基地被称为 强化 如果至少有一名士兵居住在其中。你的任务是找到在第 $$$m$$$ 天结束时你可以拥有的最大数量的强化基地(包括本垒)。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。
输出
对于每个测试用例,打印在第 $$$m$$$ 天结束时可以强化的最大碱基数。
示例
输入复制
73 1 33 3 24 2 23 2 14 3 37 7 4100000 1000000000 100000
输出复制
233236100000
注意
在第二个测试用例中,这是强化 $$$3$$$ 基地的一种方法:
- 第一天,命令基地$$$3$$$的$$$0$$$士兵移动到基地$$$2$$$。一天结束时,一名新士兵移至 $$$2$$$ 基地(现在 $$$2$$$ 基地有 $$$2$$$ 士兵,任何其他基地有 $$$0$$$ 士兵)。
- 第二天,命令基地$$$2$$$的$$$1$$$士兵移动到基地$$$1$$$。一天结束时,一名新士兵移至基地 $$$2$$$。现在基地 $$$2$$$ 有 $$$2$$$ 士兵,基地 $$$1$$$ 有 $$$1$$$ 士兵。
- 第三天,命令基地$$$2$$$的$$$2$$$士兵移动到基地$$$3$$$。一天结束时,一名新士兵移至基地 $$$2$$$。现在基地$$$1$$$和$$$2$$$有$$$1$$$士兵,基地$$$3$$$有$$$2$$$士兵。
- 现在每个基地至少有一名士兵$$$1$$$、$$$2$$$、$$$3$$$。因此,答案是$$$3$$$。
在第三个测试用例中,这是一种可以强化 $$$3$$$ 基地的方法:
- 第一天,命令现有士兵从基地 $$$2$$$ 移动到基地 $$$3$$$。一天结束时,一名新士兵移至基地 $$$2$$$。
- 第二天,命令$$$2$$$基地的士兵转移到$$$1$$$基地。一天结束时,一名新士兵移至基地 $$$2$$$。
- 现在每个基地 $$$1,2,3$$$ 都有一名士兵。因此,答案是$$$3$$$。可以证明,到一天结束时,我们不能拥有超过 $$$3$$$ 的强化基地 $$$2$$$。
下面是对第三个测试用例的生动解释。