有 $$$n$$$ 人参加有关 VOCALOID 的节目。他们将坐在一排座位上,从左到右编号为 $$$1$$$ 到 $$$m$$$。
$$$n$$$ 的人过来按顺序就座。每个人通过以下三种方式之一占据座位:
1. 坐在最左边已就座者左侧的座位上,或者如果座位 $$$1$$$ 已被占用,则离开演出。如果当前没有人坐在座位上,请坐$$$m$$$。
2. 坐在最右边已就座者右侧的座位上,或者如果座位 $$$m$$$ 已被占用,则离开演出。如果当前没有人坐在座位上,请坐在 $$$1$$$ 座位上。
3. 坐在编号为 $$$x_i$$$ 的座位上。如果这个座位被占用,则离开演出。
现在你想知道,如果你可以让人们以任意顺序进入演出,最多可以入座多少人?
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 10^5$$$) — 人数和座位数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$x_1, x_2, \ldots, x_n$$$ ($$$-2 \le x_i \le m$$$, $$$x_i \ne 0$$$),其中第 $$$i$$$ 描述了第 $$$i$$$ 个人占据座位的方式:
1. 如果$$$x_i=-1$$$,则第$$$i$$$人按第一种方式入座。
2. 如果$$$x_i=-2$$$,则第$$$i$$$人按第二种方式入座。
3. 如果 $$$x_i > 0$$$,则第 $$$i$$$ 人以第三种方式入座,即他想坐在编号为 $$$x_i$$$ 的座位上,或者如果座位被占用则离开演出。
保证所有测试用例的 $$$n$$$ 总和和 $$$m$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,输出一个整数——可以占用座位的最大人数。
示例
输入 #1
10 3 10 5 5 5 4 6 1 -2 -2 1 5 7 -1 -1 4 -2 -2 6 7 5 -2 -2 -2 -2 -2 6 6 -1 1 4 5 -1 4 6 8 -1 -1 -1 3 -1 -2 6 7 5 -1 -2 -2 -2 -2 3 1 -2 -2 1 2 5 5 -2 1 2 -1
输出 #1
1 3 5 6 5 5 5 1 2 1
注意
在第一个测试用例中,所有人都想占据 $$$5$$$ 座位,因此只有 $$$1$$$ 人可以占据该座位。
在第二个测试用例中,我们可以按 $$$1, 2, 3, 4$$$ 的顺序让人们入座,然后除了最后一个人之外的所有人都可以入座。
在第三个测试用例中,我们可以让人们按以下顺序进入节目:
让第三人进来:
–––3–––
让第四个人进来:
–––34––
让第五个人进来:
–––345–
让第一个人进来:
––1345–
让第二个人进来:
–21345–
因此,所有 $$$5$$$ 的人都入座了。
在第五个测试用例中,我们可以按以下顺序让人们进入节目:
让第四个人进来:
––––4–
让第三人进来:
–––34–
让第六个人进来,他将离开演出,因为他以第三种方式占据了第三个座位,并且必须坐在 $$$4$$$ 座位上,但它已经被占用了:
–––34–
让第五个人进来:
––534–
让第一个人进来:
–1534–
让第二个人进来:
21534–
因此,$$$5$$$ 的人入座。
在第七个测试用例中,我们可以按以下顺序让人们进入节目:
让第三人进来:
3––––––
让第四个人进来:
34–––––
让第五个人进来:
345––––
让第六个人进来:
3456–––
让第一个人进来:
34561––
让第二个人进来,他会离开演出,因为他占据了第一条路,但$$$1$$$座位已被占用:
34561––
因此,$$$5$$$ 人入座。