CF1497B M-arrays

给定一个由 $n$ 个正整数组成的数组 $a_1, a_2, \ldots, a_n$，以及一个正整数 $m$。 你需要将该数组的元素划分为若干个数组。你可以任意排列新数组中的元素顺序。 我们称一个数组是 $m$ 可整除的，如果对于数组中任意一对相邻的数（即对于每个 $i$，位置 $i$ 和 $i+1$ 的两个数），它们的和能被 $m$ 整除。只有一个元素的数组也是 $m$ 可整除的。 请你求出，最少需要多少个 $m$ 可整除的数组，才能将 $a_1, a_2, \ldots, a_n$ 划分完毕。

第一行包含一个整数 $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$。

对于每个测试用例，输出一个答案。

在第一个测试用例中，可以将元素划分如下： - $[4, 8]$。这是一个 $4$ 可整除的数组，因为 $4+8$ 能被 $4$ 整除。 - $[2, 6, 2]$。这是一个 $4$ 可整除的数组，因为 $2+6$ 和 $6+2$ 都能被 $4$ 整除。 - $[9]$。这是一个 $4$ 可整除的数组，因为它只有一个元素。 由 ChatGPT 4.1 翻译