ASD and FGH are playing a game in which both take turns and asks each other to solve a Problem.Now it is ASD's turn.So ASD asked FGH to solve the following problem.He gave FGH an Array A containing N positive integers A1,A2,A3,.....,AN and asked him to calculate MGCDK(A).
Here MGCDK(A) is the Modified GCD of Order K for Array A.
Modified GCD of Order K for an array is the Maximum number that divides at least Ceil(N/K) number of elements of the array.For example Modified Gcd of Order 2 for array A is the Maximum number that divides at least half of its elements.
Here Ceil(x) means,x rounded up to the nearest positive integer.Ceil Function
FGH is unable solve this Problem and is asking for your help.Help him.
INPUT:
OUTPUT:
Print a single line Containg a Positive Integer MGCDK(A).
CONSTRAINTS:
1≤N≤105
1≤K≤5
1≤Ai≤1012
In the above sample case 8 divides 5 elements of the array (24,8,48,56,16),Which is ≥Ceil(8/3)=3.There is no number greater than 8 that divides at least 3 numbers of the array.So 8 is the required answer.