题目内容

装配轨道上的工位排成一条没有尽头的直线。手头共有 $c$ 种喷码配方，第 $j$ 种配方绑定步长 $p_j$。打标约定如下：只要工位 $y$ 被第 $j$ 种配方覆盖，工位 $y-p_j$ 与工位 $y+p_j$ 也得用同一种配方覆盖（把这条约定不断套用下去）。

换个说法，工位的下标取遍全体整数 $(\dots,-2,-1,0,1,2,\dots)$，向两侧没有边界。一旦下标 $y\ (y\in \mathbb Z)$ 打上第 $j$ 种配方，下标 $y-p_j$ 与 $y+p_j$ 同样要打该配方，并把同一约定一直套用开。

喷码头有固定扫描节奏，因此允许你先定下一个正整数 $H$ 当作“扫描周期”。$H$ 一经确定，下面两条要一起成立：

• 只有步长能被 $H$ 整除的配方才准启用（也就是 $p_j$ 必须写成 $H$ 的整数倍）；
• 真正启用的那些配方，各自第一次起喷的工位（约定里的 $y$）对 $H$ 取模之后两两不能相同。

任意一个工位最多承接一种配方，部分工位可以空着不打。目标是让真正派上用场的配方种数尽量大，并给出这个最大种数。

输入描述

一份测试里会有若干组数据。首行单独给出整数 $g$（$1\le g\le 2\times 10^5$），表示一共有多少组。

随后共 $g$ 行，每行对应一组：先给出整数 $c$（$1\le c\le 2\times 10^5$），同一行内紧接着 $c$ 个整数 $p_1,p_2,\dots,p_c$（$1\le p_j\le 2\times 10^5$）。

保证全部组内 $c$ 相加不超过 $3\times 10^5$。

输出描述

输出一行，包含 $g$ 个整数，相邻两项以空格分隔，依次表示每一组最多能派上用场的配方种数。

样例1

输入

2
6 2 4 6 8 10 12
5 3 3 6 9 15

输出

3 3

说明

第一组取 $H=4$。步长为 $4$ 的倍数的配方是 $4,8,12$，共三种。扫描周期等于 $4$ 时至多安排 $4$ 路互不冲突的起喷，故这一选择能启用 $3$ 种。其余 $H$ 都到不了 $3$，因此答案是 $3$。

第二组取 $H=3$。五个步长都能被 $3$ 整除，但扫描周期只有 $3$ 个互异剩余类，故最多启用 $3$ 种。其余 $H$ 更差，答案也是 $3$。