题目描述

给定一个长度为 $n$ 的序列 $a_1,a_2,\ldots,a_n$。

你需要选定一个整数 $k$ $(1\leq k\leq n)$，然后对序列进行任意次操作，每次操作可以选择序列中 $k$ 个不同的位置，使得这些位置的数乘上一个相同的非零整数，最终使得序列中所有的数相等。

输出满足条件的 $k$ 的最大值。

输入格式

本题包含多组数据。第一行输入一个整数 $T$ $(1\leq T\leq 10^4)$，表示数据组数。

对于每组数据，第一行输入一个整数 $n$ $(1\leq n\leq 10^5)$，表示序列的长度。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$ $(1\leq a_i\leq 10^9)$，表示给定的序列。

保证所有数据的 $n$ 之和不超过 $10^6$。

输出格式

对于每组数据，输出一个整数，表示满足条件的 $k$ 的最大值。

1
3
2 6 2

2