P10337 [UESTCPC 2024] Operation Sequence

You are given a sequence $a_1,a_2,\ldots,a_n$ of length $n$. You need to choose an integer $k$ $(1\leq k\leq n)$, and then perform any number of operations on the sequence. In each operation, you can choose $k$ different positions in the sequence, and multiply the numbers at these positions by the same non-zero integer. In the end, make all numbers in the sequence equal. Output the maximum $k$ that satisfies the requirement.

This problem contains multiple test cases. The first line contains an integer $T$ $(1\leq T\leq 10^4)$, representing the number of test cases. For each test case, the first line contains an integer $n$ $(1\leq n\leq 10^5)$, representing the length of the sequence. The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ $(1\leq a_i\leq 10^9)$, representing the given sequence. It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

For each test case, output one integer, representing the maximum $k$ that satisfies the requirement.

Translated by ChatGPT 5