A number is said to be square-free if there does not exist any divisor of the number greater than 1 which is a perfect square number.

You are given $$N$$ integers denoted by array $$A$$.

You need to find the size $$P$$ of the largest subset of these integers such that all integers in the subset are divisible by a common square-free number that is there exists a square-free number $$x$$ which is a divisor of all the numbers present in the subset. Also, you need to find the number of such square-free numbers for which there exists a subset of size $$P$$ such that every integer in the subset is divisible by that square-free number.

Note: 1 is not considered square-free.

Input format

The first line contains an integer $$T$$ denoting the number of test cases.
The first line of each test case contains an integer $$N$$.
The second line of each test case contains $$N$$ space-separated integers denoting array $$A$$.

Output format

For each test case in a new line, print two space-separated integers where the first integer denotes the value of $$P$$ and the second integer denotes the number of square-free numbers for which there exists a subset of $$N$$ integers of size $$P$$ such that every integer in the subset is divisible by that square-free number.

Constraints

\(1 \le T \le 10 \\ 1 \le N \le 10^4 \\ 1 \le A[i] \le 10^9\)