Vasya 有两个爱好 - 向数组添加排列$$$^{\dagger}$$$ 以及查找最常出现的元素。最近,他发现了一个数组$$$a$$$,并决定在对数组$$$a$$$添加一些排列后,找出与数组$$$a$$$中相同数量的元素的最大数量。
更正式地说,Vasya 必须恰好选择一个长度为 $$$n$$$ 的排列 $$$p_1, p_2, p_3, \ldots, p_n$$$,然后根据规则 $$$a_i := a_i + p_i$$$ 更改数组 $$$a$$$ 的元素。之后,Vasya 计算每个数字在数组 $$$a$$$ 中出现的次数,并取这些值中的最大值。你需要确定他可以获得的最大值。
$$$^{\dagger}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — 测试用例的数量。然后是测试用例的描述。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个数字——在添加排列操作后等于相同数字的元素的最大数量。
示例
输入 #1
7 2 1 2 4 7 1 4 1 3 103 102 104 5 1 101 1 100 1 5 1 10 100 1000 1 2 3 1 3 1000000000 999999997 999999999
输出 #1
2 2 3 2 1 1 2
注意
在第一个测试用例中,最佳选择 $$$p = [2, 1]$$$。那么应用该运算后,数组$$$a$$$将是$$$[3, 3]$$$,其中数字$$$3$$$出现了两次,所以答案是$$$2$$$。
在第二个测试用例中,最佳选项之一是 $$$p = [2, 3, 1, 4]$$$。应用该操作后,数组 $$$a$$$ 将变为 $$$[9, 4, 5, 5]$$$。由于数字 $$$5$$$ 出现了两次,所以答案是 $$$2$$$。