CF1497B.M-arrays

You are given an array $a_1, a_2, \ldots, a_n$ consisting of $n$ positive integers and a positive integer $m$.

You should divide elements of this array into some arrays. You can order the elements in the new arrays as you want.

Let's call an array $m$-divisible if for each two adjacent numbers in the array (two numbers on the positions $i$ and $i+1$ are called adjacent for each $i$) their sum is divisible by $m$. An array of one element is $m$-divisible.

Find the smallest number of $m$-divisible arrays that $a_1, a_2, \ldots, a_n$ is possible to divide into.

给你一个由 $n$ 个正整数组成的数组 $a_1, a_2, \ldots, a_n$，以及一个正整数 $m$。

你需要将该数组的元素划分到若干个新数组中。你可以在每个新数组中任意排列其元素。

我们称一个数组是 $m$-可分的，当且仅当该数组中每一对相邻元素（即对每个 $i$，位置 $i$ 和 $i+1$ 上的两个数）之和都能被 $m$ 整除。仅含一个元素的数组总是 $m$-可分的。

求将 $a_1, a_2, \ldots, a_n$ 划分为 $m$-可分数组时，所需的最少数组个数。

The first line contains a single integer $t$ $(1 \le t \le 1000)$ — the number of test cases.

The first line of each test case contains two integers $n$, $m$ $(1 \le n \le 10^5, 1 \le m \le 10^5)$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ $(1 \le a_i \le 10^9)$.

It is guaranteed that the sum of $n$ and the sum of $m$ over all test cases do not exceed $10^5$.

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$、$m$（$1 \le n \le 10^5$，$1 \le m \le 10^5$）。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）。

保证所有测试用例中 $n$ 的总和与 $m$ 的总和均不超过 $10^5$。

For each test case print the answer to the problem.

对于每个测试用例，输出该问题的答案。

In the first test case we can divide the elements as follows:

• $[4, 8]$. It is a $4$-divisible array because $4+8$ is divisible by $4$.
• $[2, 6, 2]$. It is a $4$-divisible array because $2+6$ and $6+2$ are divisible by $4$.
• $[9]$. It is a $4$-divisible array because it consists of one element.

在第一个测试用例中，我们可以将元素按如下方式划分：

• $[4, 8]$。它是一个 $4$-可整除数组，因为 $4+8$ 能被 $4$ 整除。
• $[2, 6, 2]$。它是一个 $4$-可整除数组，因为 $2+6$ 和 $6+2$ 都能被 $4$ 整除。
• $[9]$。它是一个 $4$-可整除数组，因为它仅包含一个元素。