You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

数组是一条很长的路，每个数都在路上慢慢往前走：走一步，就变成 $|a_i-2|$。

有的数走了很久才停下，有的数走到最尽头，在同一个地方来回摆动 —— 像两个人约好碰面，却总是在同一处错过。

只有在同一个时刻、站在同一个数字上的数，才算真正遇见。

题目描述

给定数组 $a_1,a_2,\dots,a_n$。你可以执行下面的操作 任意次（也可以一次都不做）：

同时对所有下标 $i\ (1\le i\le n)$，令 $a_i = |a_i - 2|$。

注意操作是同时对每个下标做的 —— 一次操作之后，数组里每个数都会变。

设你一共执行了 $k$ 次操作（$k \ge 0$），记操作后的数组为 $b$。请求出执行若干次操作之后，数组中任意一个数字能够达到的最大出现次数

输入格式

第一行一个整数 $t$（$1 \le t \le 10^4$），表示测试用例数量。

接下来每组测试用例两行：

• 第一行一个整数 $n$（$1 \le n \le 2\times 10^5$）；
• 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1 \le a_i \le 10^9$）。

保证所有测试用例的 $n$ 之和不超过 $2\times 10^5$。

输出格式

对每组测试用例输出一行一个整数，表示答案。

样例

输入

5
2
1 3
4
1 1 1 2
3
6 7 8
4
2 2 2 2
5
1 10 100 1000 100000

输出

2
3
1
4
3

样例解释

第 1 组：操作一次得到 $[\,|1-2|,\ |3-2|\,] = [1,1]$，数字 $1$ 出现 $2$ 次。而 $k=0$ 时两个数互不相同，所以答案是 $2$。

第 2 组：答案是 $3$。其实一次都不操作时就已经有三个 $1$ 了 —— $1$ 是不动点（$|1-2|=1$），而 $2$ 只会一直待在 $2$ 和 $0$ 之间，永远不会变成 $1$，所以无论操作多少次都凑不出 $4$ 个相同的数。

第 3 组：答案是 $4$。注意 一次都不操作也算（$k=0$ 是合法的），此时四个 $2$ 已经全体相同。

数据范围与约定

• $1 \le t \le 10^4$；
• $1 \le n \le 2\times 10^5$，且所有测试用例的 $n$ 之和 $\le 2\times 10^5$；
• $1 \le a_i \le 10^9$；
• 操作次数 $k$ 可以任取（包括 $k=0$），没有上限。