本题是在验 【UR #32】王之钦定 时的产物，不排除有更优秀更简单的做法，如果有欢迎联系管理员。

数据也是乱造的，如果有疑问也欢迎联系管理员。

---

跳蚤国计算机协会 UOI 主席 “王中王” 认为 UOI 决赛不具有观赏性。

比如蟋蟀国的比赛，选手都需要在初赛快速 AK 才能晋级决赛，但 UOI 决赛只需要通过不到一半的题目就可以获得三十二强。

但是经过 UOI 系列委员会的商讨，比赛难度并没有被下调，因此王中王决定黑幕一些比赛结果。

具体来说，UOI 决赛总 $n$ 天，有 $m$ 名选手参加。现在王中王通过第六感得知，如果不加干预第 $i$ 天的比赛，那么第 $a_i$ 位选手将会胜出。但某些天王中王可以将当天题目提前透露给任意一名选手，让获得题目的选手将成为那天比赛的胜利者。王中王不需要付出任何代价。其余天数，王中王无法将题目透露给选手。

不妨假设黑幕后每天的胜者依次为 $b_1, b_2, \dots, b_n$。王中王相信观众更喜欢看到“绝对强者”之间的对决，因此他认为一段赛程 $[l, r]$ 是“好看”的，当且仅当在该段赛程中，成为过胜者的选手数不超过二，即 $|\{b_l, b_{l+1}, \dots, b_r\}| \leq 2$。

而每一段“好看”的赛程，王中王认为都会让比赛的合理性增加 $1$。

由于王中王已经达到了力量的巅峰，UOI 决赛不再面临着缺投倒闭的风险，因此王中王只想知道对于所有整个序列，比赛的合理性最高能是多少？

输入格式

第一行一个正整数 $T$，表示数据组数。

第一行两个正整数 $n,m$。

第二行 $n$ 个正整数 $a_1, a_2, \dots, a_n$，若 $a_i=-1$ 则表示王中王可以任意改变这天的比赛结果，否则这天的比赛结果固定为 $a_i$。

输出格式

每组数据一行一个数，表示整个序列的答案。

2
9 9
9 9 -1 2 -1 -1 -1 5 3
8 8
6 -1 -1 -1 7 -1 3 7

36
34

数据范围

$1 \leq n \leq 10^6,\sum n\le10^6, -1 \leq a_i \leq m\leq n$，$a_i\neq0$。

时间限制：$2\texttt{s}$

空间限制：$1\texttt{GB}$