给定一个数组 $$$a_1, a_2, \ldots, a_n$$$,由 $$$n$$$ 正整数和一个正整数 $$$m$$$ 组成。
您应该将此数组的元素划分为一些数组。您可以根据需要对新数组中的元素进行排序。
如果对于数组中的每两个相邻数字(位置 $$$i$$$ 和 $$$i+1$$$ 上的两个数字被称为每个 $$$i$$$ 相邻),我们称数组 $$$m$$$ 可整除,它们的总和可被 $$$m$$$ 整除。一个元素的数组是 $$$m$$$ 整除的。
找到 $$$a_1, a_2, \ldots, a_n$$$ 可以分成的最小数量的 $$$m$$$ 可整数组。
输入
第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,打印问题的答案。
示例
输入 #1
4 6 4 2 2 8 6 9 4 10 8 1 1 1 5 2 4 4 8 6 7 1 1 666 2 2 2 4
输出 #1
3 6 1 1
注意
在第一个测试用例中,我们可以将元素划分如下:
- $$$[4, 8]$$$。它是一个 $$$4$$$ 可整除的数组,因为 $$$4+8$$$ 可以被 $$$4$$$ 整除。
- $$$[2,6,2]$$$。它是一个 $$$4$$$ 可整除的数组,因为 $$$2+6$$$ 和 $$$6+2$$$ 可以被 $$$4$$$ 整除。
- $$$[9]$$$。它是一个 $$$4$$$ 可整除的数组,因为它由一个元素组成。