Mảng chia hết cho M

Cho một mảng $a_1,a_2,\dots ,a_n$ gồm $n$ số nguyên dương và một số nguyên dương $m$.

Bạn cần chia toàn bộ các phần tử của mảng thành một số mảng con. Trong mỗi mảng con, bạn được tự do sắp xếp thứ tự các phần tử theo ý muốn.

Một mảng được gọi là chia hết cho $m$ nếu với mọi cặp phần tử đứng cạnh nhau (hai phần tử ở vị trí $i$ và $i+1$ được xem là cạnh nhau), tổng của chúng chia hết cho $m$. Một mảng chỉ gồm đúng một phần tử luôn được xem là chia hết cho $m$.

Hãy tìm số lượng mảng con ít nhất mà ta có thể chia mảng $a$ thành, sao cho mỗi mảng con đều chia hết cho $m$.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $t$ là số lượng bộ dữ liệu.
• Với mỗi bộ dữ liệu:
  • Dòng đầu chứa hai số nguyên $n$ và $m$.
  • Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên là số lượng mảng con chia hết cho $m$ ít nhất.

Ràng buộc

• $1\le t\le 1000$
• $1\le n\le {10}^5$
• $1\le m\le {10}^5$
• $1\le a_i\le {10}^9$
• Tổng của tất cả $n$ và tổng của tất cả $m$ trên mọi bộ dữ liệu đều không vượt quá ${10}^5$.

Ví dụ