D. Zero Remainder Array

链接：https://codeforces.com/contest/1374/problem/D

You are given an array aa consisting of nn positive integers.

Initially, you have an integer x=0x=0. During one move, you can do one of the following two operations:

Choose exactly one ii from 11 to nn and increase aiai by xx (ai:=ai+xai:=ai+x), then increase xx by 11 (x:=x+1x:=x+1).
Just increase xx by 11 (x:=x+1x:=x+1).

The first operation can be applied no more than once to each ii from 11 to nn.

Your task is to find the minimum number of moves required to obtain such an array that each its element is divisible by kk (the value kk is given).

You have to answer tt independent test cases.

Input

The first line of the input contains one integer tt (1≤t≤2⋅1041≤t≤2⋅104) — the number of test cases. Then tt test cases follow.

The first line of the test case contains two integers nn and kk (1≤n≤2⋅105;1≤k≤1091≤n≤2⋅105;1≤k≤109) — the length of aa and the required divisior. The second line of the test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109), where aiai is the ii-th element of aa.

It is guaranteed that the sum of nn does not exceed 2⋅1052⋅105 (∑n≤2⋅105∑n≤2⋅105).

Output

For each test case, print the answer — the minimum number of moves required to obtain such an array that each its element is divisible by kk.

Example

input

Copy

5
4 3
1 2 1 3
10 6
8 7 1 8 3 7 5 10 8 9
5 10
20 100 50 20 100500
10 25
24 24 24 24 24 24 24 24 24 24
8 8
1 2 3 4 5 6 7 8

output

Copy

Note

Consider the first test case of the example:

x=0x=0, a=[1,2,1,3]a=[1,2,1,3]. Just increase xx;
x=1x=1, a=[1,2,1,3]a=[1,2,1,3]. Add xx to the second element and increase xx;
x=2x=2, a=[1,3,1,3]a=[1,3,1,3]. Add xx to the third element and increase xx;
x=3x=3, a=[1,3,3,3]a=[1,3,3,3]. Add xx to the fourth element and increase xx;
x=4x=4, a=[1,3,3,6]a=[1,3,3,6]. Just increase xx;
x=5x=5, a=[1,3,3,6]a=[1,3,3,6]. Add xx to the first element and increase xx;
x=6x=6, a=[6,3,3,6]a=[6,3,3,6]. We obtained the required array.

Note that you can't add xx to the same element more than once.

代码：

#include <bits/stdc++.h>
#define ll long long
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
using namespace std;
ll t,n,k,l,y,r,s,p,min1,max1,mod=1e9+7;
ll a[200001];
map<ll,ll>m;
int main()
{
	cin>>t;
	while(t--)
    {
        cin>>n>>k;
        m.clear();
        max1=0;
        p=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            a[i]%=k;
            m[k-a[i]]++;
            if(max1<m[k-a[i]]&&a[i]!=0)
            {
                max1=m[k-a[i]];
                p=k-a[i];
            }
            else if(max1==m[k-a[i]]&&a[i]!=0)
            {
                p=max(p,k-a[i]);
            }
        }
        if(max1==0)
        {
            p=0;
            max1=1;
        }
        else
            p++;
        cout<<(max1-1)*k+p<<endl;
    }
}