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$