该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在一段跨越未知星系的太空旅行中，你指挥着一支探险队，每位队员携带了一种独特的能源晶体，每种晶体都有其特定的能量值。当探险队在星际穿梭时，能源晶体会因为外界因素而产生能量波动，这些波动的总和被定义为队伍的“能量波动值”，即相邻两个晶体能量值差的绝对值之和。为了保持舰队能源系统的稳定，你需要从原始晶体序列中精心挑选出一部分，组成一个新的序列，以确保新序列的能量波动值与原序列相同，同时要求新序列尽可能短。

你的任务是构建一个晶体能量序列，以满足以下所有条件：

• 该序列至少包含一个晶体；
• 该序列是原始晶体序列的子序列，即可以通过从原始序列中删除一些晶体来获得（也可以不删除）；
• 该序列的能量波动值等同于原始序列的能量波动值。

你需要找出满足上述条件的最短晶体能量序列的长度。

输入格式

第一行包含一个整数$t$ ($1 \le t \le 10^4$) —— 测试用例的数量。

每个测试用例的第一行包含一个整数$n$ ($1 \le n \le 3 \cdot 10^5$) —— 原始晶体序列的长度。

第二行包含$n$个整数：$a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$) —— 表示每个晶体的能量值。

所有测试用例中的$n$之和不超过$3 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数 —— 满足条件的最短晶体能量序列的长度。

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

2
1
2
3

提示

在第一个测试用例中，原始序列的能量波动值为$6$；可以选择子序列$[1, 7]$，这样子序列的能量波动值也为$6$。

在第二个测试用例中，由于原始序列的能量波动值为$0$，我们可以选择任意一个晶体作为子序列，其能量波动值也为$0$。

在第三个测试用例中，只能选择包含两个晶体的子序列。