B. Array Reoderingtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given an array a consisting of n integers.Let's call a pair of indices i, j good if 1 \le i < j \le n and \gcd(a_i, 2a_j) > 1 (where \gcd(x, y) is the greatest common divisor of x and y).Find the maximum number of good index pairs if you can reorder the array a in an arbitrary way.InputThe first line contains a single integer t (1 \le t \le 1000) — the number of test cases.The first line of the test case contains a single integer n (2 \le n \le 2000) — the number of elements in the array.The second line of the test case contains n integers a_1, a_2, \dots, a_n (1 \le a_i \le 10^5).It is guaranteed that the sum of n over all test cases does not exceed 2000.OutputFor each test case, output a single integer — the maximum number of good index pairs if you can reorder the array a in an arbitrary way.ExampleInput
3
4
3 6 5 3
2
1 7
5
1 4 2 4 1
Output
4
0
9
NoteIn the first example, the array elements can be rearranged as follows: [6, 3, 5, 3].In the third example, the array elements can be rearranged as follows: [4, 4, 2, 1, 1].
3
4
3 6 5 3
2
1 7
5
1 4 2 4 1

4 0 9 
['brute force', 'greedy', 'math', 'number theory', 'sortings', '*900']