B. M-arrays

B. M-arrays

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array a1,a2,…,ana1,a2,…,an consisting of nn positive integers and a positive integer mm.

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 mm-divisible if for each two adjacent numbers in the array (two numbers on the positions ii and i+1i+1 are called adjacent for each ii) their sum is divisible by mm. An array of one element is mm-divisible.

Find the smallest number of mm-divisible arrays that a1,a2,…,ana1,a2,…,an is possible to divide into.

Input

The first line contains a single integer tt (1≤t≤1000)(1≤t≤1000)  — the number of test cases.

The first line of each test case contains two integers nn, mm (1≤n≤105,1≤m≤105)(1≤n≤105,1≤m≤105).

The second line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤109)(1≤ai≤109).

It is guaranteed that the sum of nn and the sum of mm over all test cases do not exceed 105105.

Output

For each test case print the answer to the problem.

Example

input

Copy

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

output

Copy

3
6
1
1

Note

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

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

========================================================================

比较有意思，其实就是统计模数的个数，模数n与m-n进行交叉组合，差值绝对值在1之内能够完全匹配，否则就会有剩余。特判0，m/2，当前模数个数为0的情况即可

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>

using namespace std;
typedef long long ll;


int cnt[100000+10];
int main()
{

    int t;

    cin>>t;

    while(t--)
    {
        int n;
        cin>>n;

        int m;

        cin>>m;

        for(int i=0;i<m;i++)
        {
            cnt[i]=0;
        }
        for(int i=1;i<=n;i++)
        {
            int x;
            cin>>x;

            x%=m;
            cnt[x]++;
        }

        int ans=0;

        if(cnt[0])
            ans++;


        for(int i=1;i<=m/2;i++)
        {
            if(i*2==m&&cnt[i])
            {
                ans+=1;

                break;
            }


            int now=cnt[i];

            int temp=cnt[m-i];

            if(!cnt[i])
            {
                ans+=temp;

            }
            else if(now==temp)
            {
                ans+=1;

            }
            else if(now-temp>=1)
            {
                now-=(temp+1);

                ans+=1;

                ans+=now;
            }
            else if(temp-now>=1)
            {
                temp-=(now+1);
                ans+=1;
                ans+=temp;
            }


        }

        cout<<ans<<endl;
    }
    return 0;
}