#include <bits/stdc++.h>
using namespace std;
bool CMP(int a, int b) { return a > b; }
long long int p = 1e9 + 7;
long long int power2(long long int n) {
  long long int res = 1;
  for (long long int i = 1; i <= n; i++) res *= 2;
  return res;
}
long long int power(long long int x, long long int y) {
  long long int res = 1;
  x = x % p;
  if (x == 0) return 0;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
long long int cnt1 = 0, u, cnt = 0, n;
vector<vector<long long int>> adj1(200010);
vector<pair<long long int, long long int>> adj[200010];
vector<long long int> wt(200010);
long long int visi[310068], vis[300100], last1[10000];
vector<long long int> viso;
bool ok = false;
long long int m, ans = 0;
long long int dp[200010];
bool mycompare(string s, string t) {
  string x = s + t;
  string y = t + s;
  if (x > y)
    return 1;
  else
    return 0;
}
long long int maxi = 1e7;
set<long long int> w;
pair<long long int, long long int> rotate(long long int x, long long int y,
                                          long long int a, long long int b,
                                          long long int t) {
  long long int i;
  for (i = 0; i < t; i++) {
    long long int p = a + b - y, q = x + b - a;
    x = p, y = q;
  }
  pair<long long int, long long int> P = make_pair(x, y);
  return P;
}
long long int dist(long long int x1, long long int y1, long long int x2,
                   long long int y2) {
  long long int d = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
  return d;
}
bool check(long long int x1, long long int y1, long long int x2,
           long long int y2, long long int x3, long long int y3,
           long long int x4, long long int y4) {
  long long int d2 = dist(x1, y1, x2, y2);
  long long int d3 = dist(x1, y1, x3, y3);
  long long int d4 = dist(x1, y1, x4, y4);
  if (d2 == 0 || d3 == 0 || d4 == 0) return false;
  if (d2 == d3 && d4 == 2 * d2 &&
      2 * dist(x2, y2, x4, y4) == dist(x2, y2, x3, y3))
    return true;
  if (d3 == d4 && d2 == 2 * d3 &&
      2 * dist(x2, y2, x3, y3) == dist(x3, y3, x4, y4))
    return true;
  if (d2 == d4 && d3 == 2 * d2 &&
      2 * dist(x2, y2, x3, y3) == dist(x2, y2, x4, y4))
    return true;
  return false;
}
long long int A[20010];
class SegmentTree {
 public:
  vector<long long int> A;
  vector<long long int> tree;
  long long int n, d;
  SegmentTree(vector<long long int> &inp, long long int depth) {
    A = inp;
    d = depth;
    n = A.size();
    tree.resize(4 * n);
    build(1, 0, n - 1, d);
  }
  void build(long long int node, long long int start, long long int end,
             long long int depth) {
    if (start == end)
      tree[node] = A[start];
    else {
      long long int mid = (start + end) / 2;
      build(2 * node, start, mid, depth - 1);
      build(2 * node + 1, mid + 1, end, depth - 1);
      if (depth % 2 == 1)
        tree[node] = tree[2 * node] | tree[2 * node + 1];
      else
        tree[node] = tree[2 * node] ^ tree[2 * node + 1];
    }
  }
  void update(long long int node, long long int start, long long int end,
              long long int idx, long long int depth) {
    if (start == end) {
      tree[node] = A[start];
    } else {
      long long int mid = (start + end) / 2;
      if (start <= idx && idx <= mid)
        update(2 * node, start, mid, idx, depth - 1);
      else
        update(2 * node + 1, mid + 1, end, idx, depth - 1);
      if (depth % 2 == 1)
        tree[node] = tree[2 * node] | tree[2 * node + 1];
      else
        tree[node] = tree[2 * node] ^ tree[2 * node + 1];
    }
  }
  long long int update(long long int index, long long int value) {
    A[index] = value;
    update(1, 0, n - 1, index, d);
    return tree[1];
  }
};
priority_queue<pair<long long int, long long int>,
               vector<pair<long long int, long long int>>,
               greater<pair<long long int, long long int>>>
    pq;
void dj(long long int s) {
  pair<long long int, long long int> pi;
  for (long long int i = 0; i < adj[s].size(); i++) {
    if (vis[adj[s][i].first] > vis[s] + adj[s][i].second) {
      vis[adj[s][i].first] = vis[s] + adj[s][i].second;
      visi[adj[s][i].first] = s;
      pq.push(make_pair(vis[adj[s][i].first], adj[s][i].first));
    }
  }
  if (pq.empty()) return;
  pi = pq.top();
  pq.pop();
  dj(pi.second);
}
void path(long long int x) {
  if (x == 0) return;
  path(visi[x]);
  cout << x << " ";
}
long long int sum[2000100] = {0};
int main() {
  long long int t = 1;
  cin >> t;
  while (t--) {
    long long int n, k;
    cin >> n >> k;
    long long int a[n + 1], i, ans = INT_MIN;
    map<long long int, long long int> mp;
    for (i = 0; i < n; i++) {
      cin >> a[i];
      if (a[i] % k != 0) {
        mp[k - a[i] % k]++;
        ans = max(ans, mp[k - a[i] % k]);
      }
    }
    long long int sum = 0;
    for (auto it : mp) {
      if (it.second == ans) {
        sum = k * (it.second - 1) + it.first + 1;
      }
    }
    cout << sum << endl;
  }
}

### Prompt

Your task is to create a Cpp solution to the following problem:

You are given an array a consisting of n positive integers.

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

  1. Choose exactly one i from 1 to n and increase a_i by x (a_i := a_i + x), then increase x by 1 (x := x + 1). 
  2. Just increase x by 1 (x := x + 1). 



The first operation can be applied no more than once to each i from 1 to n.

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

You have to answer t independent test cases. 

Input

The first line of the input contains one integer t (1 ≤ t ≤ 2 ⋅ 10^4) — the number of test cases. Then t test cases follow.

The first line of the test case contains two integers n and k (1 ≤ n ≤ 2 ⋅ 10^5; 1 ≤ k ≤ 10^9) — the length of a and the required divisior. The second line of the test case contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9), where a_i is the i-th element of a.

It is guaranteed that the sum of n does not exceed 2 ⋅ 10^5 (∑ n ≤ 2 ⋅ 10^5).

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 k.

Example

Input


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


6
18
0
227
8

Note

Consider the first test case of the example:

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



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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
bool CMP(int a, int b) { return a > b; }
long long int p = 1e9 + 7;
long long int power2(long long int n) {
  long long int res = 1;
  for (long long int i = 1; i <= n; i++) res *= 2;
  return res;
}
long long int power(long long int x, long long int y) {
  long long int res = 1;
  x = x % p;
  if (x == 0) return 0;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
long long int cnt1 = 0, u, cnt = 0, n;
vector<vector<long long int>> adj1(200010);
vector<pair<long long int, long long int>> adj[200010];
vector<long long int> wt(200010);
long long int visi[310068], vis[300100], last1[10000];
vector<long long int> viso;
bool ok = false;
long long int m, ans = 0;
long long int dp[200010];
bool mycompare(string s, string t) {
  string x = s + t;
  string y = t + s;
  if (x > y)
    return 1;
  else
    return 0;
}
long long int maxi = 1e7;
set<long long int> w;
pair<long long int, long long int> rotate(long long int x, long long int y,
                                          long long int a, long long int b,
                                          long long int t) {
  long long int i;
  for (i = 0; i < t; i++) {
    long long int p = a + b - y, q = x + b - a;
    x = p, y = q;
  }
  pair<long long int, long long int> P = make_pair(x, y);
  return P;
}
long long int dist(long long int x1, long long int y1, long long int x2,
                   long long int y2) {
  long long int d = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
  return d;
}
bool check(long long int x1, long long int y1, long long int x2,
           long long int y2, long long int x3, long long int y3,
           long long int x4, long long int y4) {
  long long int d2 = dist(x1, y1, x2, y2);
  long long int d3 = dist(x1, y1, x3, y3);
  long long int d4 = dist(x1, y1, x4, y4);
  if (d2 == 0 || d3 == 0 || d4 == 0) return false;
  if (d2 == d3 && d4 == 2 * d2 &&
      2 * dist(x2, y2, x4, y4) == dist(x2, y2, x3, y3))
    return true;
  if (d3 == d4 && d2 == 2 * d3 &&
      2 * dist(x2, y2, x3, y3) == dist(x3, y3, x4, y4))
    return true;
  if (d2 == d4 && d3 == 2 * d2 &&
      2 * dist(x2, y2, x3, y3) == dist(x2, y2, x4, y4))
    return true;
  return false;
}
long long int A[20010];
class SegmentTree {
 public:
  vector<long long int> A;
  vector<long long int> tree;
  long long int n, d;
  SegmentTree(vector<long long int> &inp, long long int depth) {
    A = inp;
    d = depth;
    n = A.size();
    tree.resize(4 * n);
    build(1, 0, n - 1, d);
  }
  void build(long long int node, long long int start, long long int end,
             long long int depth) {
    if (start == end)
      tree[node] = A[start];
    else {
      long long int mid = (start + end) / 2;
      build(2 * node, start, mid, depth - 1);
      build(2 * node + 1, mid + 1, end, depth - 1);
      if (depth % 2 == 1)
        tree[node] = tree[2 * node] | tree[2 * node + 1];
      else
        tree[node] = tree[2 * node] ^ tree[2 * node + 1];
    }
  }
  void update(long long int node, long long int start, long long int end,
              long long int idx, long long int depth) {
    if (start == end) {
      tree[node] = A[start];
    } else {
      long long int mid = (start + end) / 2;
      if (start <= idx && idx <= mid)
        update(2 * node, start, mid, idx, depth - 1);
      else
        update(2 * node + 1, mid + 1, end, idx, depth - 1);
      if (depth % 2 == 1)
        tree[node] = tree[2 * node] | tree[2 * node + 1];
      else
        tree[node] = tree[2 * node] ^ tree[2 * node + 1];
    }
  }
  long long int update(long long int index, long long int value) {
    A[index] = value;
    update(1, 0, n - 1, index, d);
    return tree[1];
  }
};
priority_queue<pair<long long int, long long int>,
               vector<pair<long long int, long long int>>,
               greater<pair<long long int, long long int>>>
    pq;
void dj(long long int s) {
  pair<long long int, long long int> pi;
  for (long long int i = 0; i < adj[s].size(); i++) {
    if (vis[adj[s][i].first] > vis[s] + adj[s][i].second) {
      vis[adj[s][i].first] = vis[s] + adj[s][i].second;
      visi[adj[s][i].first] = s;
      pq.push(make_pair(vis[adj[s][i].first], adj[s][i].first));
    }
  }
  if (pq.empty()) return;
  pi = pq.top();
  pq.pop();
  dj(pi.second);
}
void path(long long int x) {
  if (x == 0) return;
  path(visi[x]);
  cout << x << " ";
}
long long int sum[2000100] = {0};
int main() {
  long long int t = 1;
  cin >> t;
  while (t--) {
    long long int n, k;
    cin >> n >> k;
    long long int a[n + 1], i, ans = INT_MIN;
    map<long long int, long long int> mp;
    for (i = 0; i < n; i++) {
      cin >> a[i];
      if (a[i] % k != 0) {
        mp[k - a[i] % k]++;
        ans = max(ans, mp[k - a[i] % k]);
      }
    }
    long long int sum = 0;
    for (auto it : mp) {
      if (it.second == ans) {
        sum = k * (it.second - 1) + it.first + 1;
      }
    }
    cout << sum << endl;
  }
}

```