Baobao 非常喜欢唱歌，他很享受一个叫做“Singing Everywhere”的游戏，这个游戏允许玩家唱歌并根据他们的表现进行评分。

将 Baobao 演唱的歌曲视为一个整数序列 $a_1, a_2, \dots, a_n$，其中 $a_i$ 表示歌曲中的第 $i$ 个音符。如果 $1 < k < n$，$a_{k-1} < a_k$ 且 $a_{k+1} < a_k$，我们就称音符 $a_k$ 为一个“破音”。Baobao 唱出的破音越多，得分就越低。

为了获得更高的分数，Baobao 决定删除歌曲中至多一个音符。在进行此操作后，Baobao 唱出破音的最少次数是多少？

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$（约 100），表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示歌曲的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($-2^{31} \le a_i < 2^{31}$)，表示 Baobao 演唱的歌曲。

保证至多有 5 组测试数据的 $n > 100$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示答案。

样例

输入格式 1

3
6
1 1 4 5 1 4
7
1 9 1 9 8 1 0
10
2 1 4 7 4 8 3 6 4 7

输出格式 1

1
0
2

说明

对于第一个样例，Baobao 不需要删除任何音符。因为如果不删除音符，他会唱出 1 个破音（第 4 个音符），而无论他删除哪个音符，他最终也总是会唱出 1 个破音。

对于第二个样例，Baobao 可以删除第 3 个音符，这样就不会有破音了。太棒了！

对于第三个样例，Baobao 可以删除第 4 个音符，这样就只会产生 2 个破音（分别为 4 8 3 和 3 6 4）。