题目描述

这是一个由$n$个整数组成的序列：$[a_1, a_2, \dots, a_n]$。 这个序列将有一个对比值$k = |a_1-a_2|+|a_2-a_3|+\cdots+|a_{n-1}-a_n|$，当然，特别的，如果$n=1$，我们对比值默认为$0$。

那么现在问题是： 给你一个整数$a$。你的任务是构建一个子序列$b$，这是子序列$b$的要求如下：

1.$b$非空，即至少有一个元素

2.$b$是$a$的子序列，即可以从$a$中随意删除若干个元素（可以不删）

3.$b$的对比值$k$必须等于$a$的对比值。

你能找出最小长度的$b$序列吗？如果能，请输出长度。

输入

第一行包含一个整数t，代表测试样例的组数。 ($1 \le t \le 10^4$) 对于每组测试样例： 第一行包含一个整数$n$，代表数组$a$的长度。 ($1 \le n \le 3 \cdot 10^5$) 第二行包含$n$个整数，代表 $a_1, a_2, \cdot, a_n$。 ($0 \le a_i \le 10^9$) 数据保证所有的$n$总和不超过$3 \cdot 10^5$.

输出

对于每组测试样例，输出一个整数，即$b$数组的最小长度。

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