Problem Description

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.

Input Format

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$.

Output Format

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

1
3
2 6 2

2

Hint

Translated by ChatGPT 5