题目概述

• 时间限制：1000 ms
• 空间限制：128 MB
• 命题人：Stardust D.L.

题目描述

小 A 和你我一样，正坐在电脑前刷题。但茫茫多的 OJ 和茫茫多的题目，让他感到无从下手。幸运的是，小 A 得到了一个神奇的工具，能很快生成一个指定长度的题目列表，还能标识出题目的难度等级。小 A 用这个工具生成了一个长度为 \(n\) 的题目列表，但这个题目列表中难度安排不太令人满意，为了提高刷题体验，也尽快提高问题求解能力，小 A 决定把其中一些题换掉，来让题目难度安排更加合理。
形式化的，设题目列表 \(a\)，\(a_i(1\le i\le n)\) 表示第 \(i\) 道题的难度（数值越大，难度越高），定义 对于题目列表的“难度渐进”值 \(Q(a)\) 为：

\[Q(a)=\sum_{i=2}^n \min(1,a_i-a_{i-1})\]

小 A 希望将 某一些 \(a_i\) 改成 \(a_i'\)（由于可以任意挑题目，所以这里选取的 \(a_i'\in \mathbb{Z}\) 是任意的，即使是负值也可以），使得修改后的新序列 \(a'\)，\(Q(a')\) 最大。为了尽快开始做题，小 A 希望被替换的题目数量越少越好。请求出最少替换几道题目能使得 \(Q(a')\) 最大。

输入

第一行一个整数 \(T\)，表示 \(T\) 组测试数据。
之后对于每组测试数据：
第一行一个整数 \(n\)，表示题目列表长度。
第二行 \(n\) 个整数 \(a_i\)，表示每道题目的难度。

输出

\(T\) 行，每行一个整数表示答案。

样例

输入

4
3
1 1 2
4
1 2 2 5
10
46 42 22 45 14 33 3 21 9 5
20
38 35 11 86 31 47 3 6 71 93 42 74 95 3 94 47 89 46 98 10

输出

1
1
8
13

解释

• 第一组：将第一个 \(1\) 改成 \(0\)
• 第二组：将第二个 \(2\) 改成 \(3\) 或 \(4\)

数据范围

• \(1\le T \le 5\)
• \(1\le n\le 3000\)
• \(1\le a_i \le 10^5,a_i\in \mathbb{Z}\)