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
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≤T≤101≤N≤1041≤A[i]≤109