思路

• 将数组按余数分组：对每个数计算 $r = a_i \bmod k$，分类到 $V_r$。

• 对于 $r = 0$ 以及（若 $k$ 为偶数）$r = \frac{k}{2}$：同类元素可以两两配对移除，最多只能留下 $1$ 个。要最大化剩余和，应移除该类中最小的 $2 \left\lfloor \frac{|V_r|}{2} \right\rfloor$ 个元素。

• 对于互补余数对 $r$ 与 $s = (k-r) \bmod k$（取 $1 \le r < s \le k-1$）：

  • 最终必须让两类中至少有一类变为空，因此必然会从两边各移除 $m = \min(|V_r|, |V_s|)$ 个元素。
  • 为使剩余和最大，移除两侧中最小的 $m$ 个元素（总移除和最小）。
  • 余下的就是较大一侧的剩余元素（或两边都空）。

• 将每个 $V_r$ 升序排序并做前缀和 $P_r$。记 $\text{sum}(V_r) = P_r[|V_r|]$。

题目内容

给定一个长度为$n$的正整数数组{$a_1,a_2,...,a_n$}，以及一个正整数$k$。 定义一次操作如下:

• 任选一对下标满足$1≦i<j≦n、(a_i+a_j)mod\ k = 0$ (即恰好能被$k$整除)，同时删除$a_i$和$a_j$。

你必须重复执行操作，直到数组中不存在这样的两个元素$a_u$和$a_v$，使得它们的和能被整除为止。

此时数组长度减少若干，你需要最大化剩余元素之和。请计算并输出该最大和。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$t(1 ≦t≦10^4)$表示数据组数，每组测试数

据描述如下: 第一行输入两个整数$n$和$k(1≦n≦2×10^5，1≦k≦ 10^9)$

第二行输入$n$个整数$a_1,a_2,,..,a_n (1 ≦ a_i ≦ 10^9)$

除此之外，保证单个测试文件的n之和不超过$2×10^5$

输出描述

对于每一组测试数据，新起一-行，输出一个整数，表示满足条件的最大数组元素之和。

样例1

输入

2
3 4 
1 7 4
5 3 
1 2 3 4 5

输出

4 
3