Half Sequence solution codechef

For Solution
Click Here!
hef has an array AA of size NN. Chef wants to choose any subsequence of size exactly ⌈N2⌉⌈N2⌉ from the array such that GCD of all the elements in that sequence must be 22. Chef names such a kind of sequence as a halfsequence.
Help Chef to find whether he would be able to select any halfsequence in the given array.
As a reminder,
 A subsequence of an array is a sequence that can be derived from the given array by deleting zero or more elements without changing the order of the remaining elements.
 GCD stands for Greatest Common Divisor. The greatest common divisor of a subsequence is the largest integer dd such that all the numbers in sequence are divisible by dd. For more information, refer to here.
 ⌈x⌉⌈x⌉ is the ceiling (round up) operation: ⌈3.5⌉=4,⌈2⌉=2⌈3.5⌉=4,⌈2⌉=2.
Half Sequence solution codechef
 The first line contains an integer TT denoting the number of test cases. The TT test cases then follow.
 The first line of each test case contains a single integer NN denoting the size of the array.
 The second line of each test case contains NN spaceseparated integers A1,A2....ANA1,A2….AN denoting the given array.
Half Sequence solution codechef
For each test case, output on one line YES
if Chef can find a halfsequence, else print NO
. Output is case insensitive.
Constraints
 1≤T≤201≤T≤20
 2≤N≤1052≤N≤105
 1≤Ai≤1091≤Ai≤109
 Sum of NN over all test cases does not exceed 105105
Half Sequence solution codechef
3
5
1 2 3 4 5
4
1 2 3 4
3
30 42 70
Sample Output 1
NO
YES
NO
Explanation

For the first test case, Chef wants to select ⌈52⌉=3⌈52⌉=3 numbers. But for any 33 numbers, GCD would not be 22. Therefore the answer is
NO
. 
For the second test case, Chef wants to select ⌈42⌉=2⌈42⌉=2 numbers. Chef can select the subsequence [2,4][2,4] with GCD of 22. Therefore the answer is
YES
. 
For the third test case, Chef wants to select ⌈32⌉=2⌈32⌉=2 numbers. But for any 22 numbers, GCD would be bigger than 22. Therefore the answer is
NO
. 
For Solution
Click Here!