A4585 | 君往何处

本题关于《节奏大师》的内容摘选自 萌娘百科，并基于题目本身进行一定修改，便于理解和阅读。

《节奏大师》 是腾讯出品的一款 移动端音乐节奏游戏，由腾讯下属的光速工作室（现已并入光子工作室群）开发。游戏最早于 $2012$ 年发行，目前的游戏版本基于 $2023$ 年重制的新版。

《节奏大师》是一款下落式音乐游戏。玩家需要根据下落的音符，做出对应的操作。除传统触摸（敲击）音符和长按（连打）音符外，《节奏大师》还加入了滑动音符和长按与滑动相结合的音符。

《节奏大师》的游戏界面中央大部分是若干条轨道，每一条轨道的底端有一个按键。游戏的目标就是配合下落音符的节奏尽量准确地点击按键。



本题「音符」只考虑「单键」操作。

单键：最基础的音符，在音符落到底端按键上时点击一下即可。若没有在音符落到按键上一定时间内点击到音符，则判为 $\tt{MISS}$。

判定：本题只考虑没有任何加成影响的「大P」判定；即当「单键」落到判定键地段的按键上的时间为 $T$ ms，那么只要在 $T - 30$ ms 到 $T + 30$ ms 的范围内点击对应的按键即可得到「大P」判定。

$\tt{AP}$：即完美演奏，指一首曲子的所有音符全部全部得到「大P」判定。

给出一首曲子所有的「单键」落到判定底端按键上的时间，你现在最多可以使用 $4$ 根手指来完成这首曲子，每根手指在完成一个「单键」的点击后，需要 $100$ ms 的反应时间，才能够完成下一次「单键」的点击操作；请你计算 $\tt{AP}$ 这首曲子最少需要使用多少根手指。

$\bf{每个测试文件包含\ T\ 个测试用例。}$

$\large{数据范围}$

- $1 \le T \le 100$
- $1 \le N \le 3000$
- $1 \le T_i \le 2 \times 10^5$
- $T_i \le T_{i + 1}\ (1 \le i \lt N)$

对于每个输入文件，输入格式如下：

$\tt{T}$

$\tt{Testcase_1}$

$\tt{Testcase_2}$

$\tt{\vdots}$

$\tt{Testcase_T}$

对于每个 $\tt{Testcase}$ 格式如下：

$\tt{N}$

$\tt{T_1\ T_2\ T_3 \cdots\ T_N}$

对于输入文件中的每个 $\tt{Testcase}$，在单独的一行中输出 $\tt{AP}$ 这首曲子需要使用的最少的手指的数量，如果使用 $4$ 根手指都无法 $\tt{AP}$，则输出 $-1$。