1

# Max GCD Pair

Difficulty: MEDIUM
Avg. time to solve
35 min
Success Rate
75%

Problem Statement
Suggest Edit

#### You are given an array of positive integers. Find the GCD(Greatest Common Divisor) of a pair of elements such that it is maximum among all possible pairs. GCD(a,b) is the maximum number x such that both a and b are divisible by x.

``````For example:
If the given array is {1,5,2,3,4}, the output will be 2 (which is GCD of 2 and 4, all other pairs have a GCD of 1)
``````
##### Input format :
``````The first line of input contains a single integer T, representing the number of test cases or queries to be run.

Then the T test cases follow.

The first line of each test case contains a positive integer N, which represents the size of the array.

The next line contains 'N' single space-separated positive integers representing the elements of the array.
``````
##### Output Format :
``````For each test case, print the maximum GCD value.
``````
##### Note:
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints :
``````1 <= T <= 10
2 <= N <= 10^4
1 <= Arr[i] <= 10^5
Where T is the number of test cases, N is the size of the array and Arr[i] is the ith element in the array.

Time Limit: 1 sec
``````
##### Sample Input 1:
``````3
5
5 2 4 3 1
5
2 4 6 5 6
10
4 2 10 8 6 4 3 2 1 7
``````
##### Sample Output 1:
``````2
6
4
``````
##### Explanation for Sample Input 1:
``````In the 1st test case, pair (2,4) has maximum GCD value 2, all other pairs have a GCD of 1.
In the 2nd test case, pair (6,6) has maximum GCD value 6, all other pairs have GCD less than 6.
In the 3rd test case, pair (4,8) has maximum GCD value 4, all other pairs have GCD less than 4.
``````
##### Sample Input 2:
``````2
4
2 4 6 8
5
1 2 3 4 5
``````
##### Sample Output 2:
``````4
2
``````