310383: CF1825C. LuoTianyi and the Show

C. LuoTianyi and the Showtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

There are $n$ people taking part in a show about VOCALOID. They will sit in the row of seats, numbered $1$ to $m$ from left to right.

The $n$ people come and sit in order. Each person occupies a seat in one of three ways:

1. Sit in the seat next to the left of the leftmost person who is already sitting, or if seat $1$ is taken, then leave the show. If there is no one currently sitting, sit in seat $m$.
2. Sit in the seat next to the right of the rightmost person who is already sitting, or if seat $m$ is taken, then leave the show. If there is no one currently sitting, sit in seat $1$.
3. Sit in the seat numbered $x_i$. If this seat is taken, then leave the show.

Now you want to know what is the maximum number of people that can take a seat, if you can let people into the show in any order?

Input

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

The first line of each test case contains two integers $n$ and $m$ ($1 \le n, m \le 10^5$) — the number of people and the number of seats.

The second line of each test case contains $n$ integers $x_1, x_2, \ldots, x_n$ ($-2 \le x_i \le m$, $x_i \ne 0$), the $i$-th of which describes the way in which the $i$-th person occupies a seat:

1. If $x_i=-1$, then $i$-th person takes the seat in the first way.
2. If $x_i=-2$, then $i$-th person takes the seat in the second way.
3. If $x_i > 0$, then the $i$-th person takes a seat in the third way, i.e. he wants to sit in the seat with the number $x_i$ or leave the show if it is occupied..

It is guaranteed that sum of $n$ and the sum of $m$ over all test cases don't exceed $10^5$.

Output

For each test case output a single integer — the maximum number of people who can occupy a seat.

ExampleInput

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

Output

1
3
5
6
5
5
5
1
2
1

Note

In the first test case, all the people want to occupy the $5$ seat, so only $1$ people can occupy the seat.

In the second test case, we can let people in order $1, 2, 3, 4$, then all but the last person can take a seat.

In the third test case, we can let people into the show in that order:

Let the third person in:

–

–

–

3

–

–

–

Let the fourth person in:

–

–

–

3

4

–

–

Let the fifth person in:

–

–

–

3

4

5

–

Let the first person in:

–

–

1

3

4

5

–

Let the second person in:

–

2

1

3

4

5

–

Thus, all $5$ people took seats.

In the fifth test case, we can let people into the show in this order:

Let the fourth person in:

–

–

–

–

4

–

Let the third person in:

–

–

–

3

4

–

Let the sixth person in, he'll leave the show because he takes the third seat the third way and has to sit in the $4$ seat, but it's already taken:

–

–

–

3

4

–

Let the fifth person in:

–

–

5

3

4

–

Let the first person in:

–

1

5

3

4

–

Let the second person in:

2

1

5

3

4

–

Thus, $5$ of people took seats.

In the seventh test case, we can let people into the show in this order:

Let the third person in:

3

–

–

–

–

–

–

Let the fourth person in:

3

4

–

–

–

–

–

Let the fifth person in:

3

4

5

–

–

–

–

Let the sixth person in:

3

4

5

6

–

–

–

Let the first person in:

3

4

5

6

1

–

–

Let the second person in, he will leave the show because he occupies the first way, but the $1$ seat is taken:

3

4

5

6

1

–

–

Thus, $5$ people took seats.

题目大意：
这是一个关于VOCALOID表演的座位安排问题。有n个人要坐在一排编号为1到m的座位上。每个人有三种占座方式：
1. 坐在已坐人的最左边或如果1号座位有人，则离开表演。如果目前没人坐着，则坐在m号座位。
2. 坐在已坐人的最右边或如果m号座位有人，则离开表演。如果目前没人坐着，则坐在1号座位。
3. 坐在编号为x_i的座位上，如果这个座位有人，则离开表演。

问题是要找出在可以任意顺序让人进入表演的情况下，最多能有多少人坐下。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。
- 每个测试用例的第一行包含两个整数n和m（1≤n, m≤10^5），分别表示人数和座位数。
- 每个测试用例的第二行包含n个整数x_1, x_2, ..., x_n（-2≤x_i≤m，x_i≠0），描述每个人的占座方式。

输出：
- 对于每个测试用例，输出一个整数，表示最多能坐下的人数。

示例输入输出已在题目中给出。题目大意： 这是一个关于VOCALOID表演的座位安排问题。有n个人要坐在一排编号为1到m的座位上。每个人有三种占座方式： 1. 坐在已坐人的最左边或如果1号座位有人，则离开表演。如果目前没人坐着，则坐在m号座位。 2. 坐在已坐人的最右边或如果m号座位有人，则离开表演。如果目前没人坐着，则坐在1号座位。 3. 坐在编号为x_i的座位上，如果这个座位有人，则离开表演。 问题是要找出在可以任意顺序让人进入表演的情况下，最多能有多少人坐下。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。 - 每个测试用例的第一行包含两个整数n和m（1≤n, m≤10^5），分别表示人数和座位数。 - 每个测试用例的第二行包含n个整数x_1, x_2, ..., x_n（-2≤x_i≤m，x_i≠0），描述每个人的占座方式。 输出： - 对于每个测试用例，输出一个整数，表示最多能坐下的人数。 示例输入输出已在题目中给出。