题目描述

$wanan学长$ 喜欢给学弟学妹讲题，但是回答的长度根据他的心情来定。为了判断 $wanan学长$ 当天的心情，以便学弟学妹问题。

我们用数组 $a$ 记录 $wanan学长$ 学长每时每刻的心情，对于一个由整数 $a_1$ , $a_2$ , $a_3$ ... $a_n$ 组成的心情数组，我们把数值 |$a_2-a_1$| +|$a_3-a_2$|+|$a_4-a_3$| +...+ |$a_n-a_n-_1$| 称为心情数组的心情值。

请注意，长度为 $1$ 的数组的心情值等于 $0$

要求将一个整数数组 $a$ 满足以下所有条件的建立一个 $b$ 数组：

• $b$ 不是空数组，即至少有一个元素；
• $b$ 是 $a$ 的子序列，即从 $a$ 中删除一些元素(可能是零)就可以得到 $b$ ；
• $b$ 的心情值等于 $a$ 的心情值。

输出数组 $b$ 的最小的长度 $w$，表示 $wanan学长$ 当天的心情。

输入

第一行一个整数 $t$，代表测试样例

每个测试样例的第一行包含一个整数 $n$，代表数组长度

第二行包含 $n$ 个整数$a_1$ , $a_2$ , $a_3$ ... $a_n$。

所有测试样例的 $n$ 之和不超过 $3$⋅$10^5$ 。

输出

每个测试用例输出一个整数，数组 $b$ 的最小的长度$w$。

样例

4
5
1 3 3 3 7
2
4 2
4
1 1 1 1
7
5 4 2 1 0 0 4

2
2
1
3

样例解释

第一个测试样例：

心情数组$a$为 $[1,3,3,3,7]$，心情值为 $|3-1| + |3-3| + |3-3| + |7-3| = 6$ , 数组 $b$ 可以为 $[1,7]$ ,心情值为 $6$ ,长度最小为 $2$.

限制

$1$ ≤ $t$ ≤ $10^4$

$1$ ≤ $n$ ≤ $3⋅10^5$

0 ≤ $a_i$ ≤ $10^9$