该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

$\red{t}$每次给定一个长度为$\red{n}$的序列$\red{a}$。定义数对$\red{(i,j)}$是优美的当且仅当$\red{1<=i <j<=n,gcd(a_i,2\times a_j)>1}$ 。请求出将原序列重排后可以产生的优美数对个数的最大值。

输入格式

第一行一个整数$\red{n，}$表示序列长度。

接下来一行$\red{n}$个整数$\red{a_i，}$表示序列。

输出格式

输出一行一个整数，表示答案。

样例

输入样例1

4
3 6 5 3

输出样例1

4

输入样例2

5
1 4 2 4 1

输出样例2

9

提示

对于$\red{50\%}$的数据，有$\red{1<=n<=20}$；

对于$\red{100\%}$的数据，有$\red{1<=n<=2000,1<=a_i<=10^5}$。