$upd\ on\ 2026.3.31$：修正了一处不准确的描述。

首先无脑暴力。用 set 维护已有数值，最坏情况下第 $i$ 次插入需要 $\mathrm O(i)$ 次尝试，时间复杂度 $\mathrm O(T n^2\log n)$，TLE。

考虑优化。容易想到每次 $+k$ 不会改变原数除以 $k$ 的余数，所以冲突都是在同一个余数类中发生的。

那么按余数分类，把商存入 vector，这样 $+k$ 就可以表示为商 $+1$。（这边注意一下 $k<0$ 的情况，正数模负数一定为正（负数模正数一定为负），被除数越小商越大，不会影响程序，不理解的可以拿个样例模拟一下。）

每一类内部排序，贪心地从小到大处理，记录当前最大值 $mx$，遇到 $\ge mx$ 的数就加到 $mx+1$。

时间复杂度 $\mathrm O(T n\log n)$。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int T,n,k,mx,x;
ll ans;
vector<int> v[N];
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&k);ans=0;
        for(int i=0;i<abs(k);i++)v[i].clear();
        for(int i=1;i<=n;i++){
            scanf("%d",&x);
            v[x%k].push_back(x/k);
        }
        for(int i=0;i<abs(k);i++){
            sort(v[i].begin(),v[i].end());
            mx=-N;
            for(int x:v[i]){
                if(x<=mx) ans+=mx+1-x,mx++;
                else mx=x;
            }
        }
		printf("%lld\n",ans);
    }
    return 0;
}