第二题 序列（xile）

题目描述

小幸有一个长度为 ( n ) 的序列 (a_1,a_2,\dots,a_n)，每个元素是 ( 1 ) 到 ( n ) 之间的整数（可能有重复）。

小幸想从 ( a ) 中选择一个子序列，满足对于子序列中的任意一对相邻元素，这两个元素的值之差等于它们在原序列中的下标之差。

形式化的即，选出一些位置构成一个递增下标序列 (p_1 < p_2 < \dots < p_k)，满足：

• 对于任意相邻的 (p_i) 和 (p_{i+1})，有 (p_{i+1} - p_i = a_{p_{i+1}} - a_{p_i})（下标差等于值的差）。

你的任务是求出，最多能选出多少个位置？

名词解释

子序列：从原序列中删除任意个（可以为零，也可以为全部）元素，且保持剩余元素相对顺序不变得到的新序列。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 (T\ (1 \le T \le 10^3)) 代表数据组数，每组测试数据描述如下：

• 第一行输入一个整数 (n\ (1 \le n \le 2 \times 10^4))。
• 第二行输入 ( n ) 个整数 (a_1,a_2,\dots,a_n\ (1 \le a_i \le n))。

除此之外，保证单个测试文件的 ( n ) 之和不超过 (2 \times 10^5)。

输出描述

对于每一组测试数据，新起一行输出一个整数，表示最多能选出的位置个数。

示例1

输入

3
5
1 2 1 4 1
6
2 2 2 2 2 2
7
1 2 3 4 5 6 7

输出

3
1
7

说明

• 对于第一组测试数据，选择 (a_1=1,\ a_2=2,\ a_4=4) 即可。
• 对于第二组测试数据，所有值相同，只能选一个位置。
• 对于第三组测试数据，整个序列满足 (p_{i+1}-p_i=1) 且 (a_{i+1}-a_i=1)，可以全选。