K. Sequence Operation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a sequence of length $$$n$$$, $$$a_1,a_2,\ldots,a_n$$$.

You need to select an integer $$$k$$$ ($$$1\leq k\leq n$$$), and then perform any number of operations on the sequence. Each operation can select $$$k$$$ different positions in the sequence, and multiply the numbers at these positions by the same non-zero integer, until all the numbers in the sequence are equal.

Output the maximum value of $$$k$$$ that satisfies the condition.

Input

This problem contains multiple test cases. The first line contains an integer $$$T$$$ ($$$1\leq T\leq 10^4$$$), indicating the number of test cases.

For each test case, the first line contains an integer $$$n$$$ ($$$1\leq n\leq 10^5$$$), indicating 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 all $$$n$$$ in the input does not exceed $$$10^6$$$.

Output

For each test case, output an integer representing the maximum value of $$$k$$$ that satisfies the condition.

Example
Input
1
3
2 6 2
Output
2