最大化 MEX

https://codeforces.com/problemset/problem/2021/B

你得到一个包含 n 个正整数的数组 a，以及一个整数 x。你可以执行任意次（可以为 0 次）如下的两步操作：

1. 选择一个索引 i（1 ≤ i ≤ n）；
2. 将 ai 增加 x，也就是令 ai := ai + x。

请你找出，在最优地执行操作后，数组 a 的 最大 MEX 值。

MEX（最小未包含值，Minimum EXcluded value）是数组中 没有出现 的最小非负整数。例如：

• [2, 2, 1] 的 MEX 是 0，因为 0 没有出现在数组中；
• [3, 1, 0, 1] 的 MEX 是 2，因为 0 和 1 出现了，但 2 没有；
• [0, 3, 1, 2] 的 MEX 是 4，因为 0, 1, 2, 3 都出现了，4 没有。

输入格式

每个测试包含多个测试用例。第一行输入一个整数 t（1 ≤ t ≤ 5000）——表示测试用例的个数。

接下来每个测试用例包含两行：

• 第一行包含两个整数 n 和 x（1 ≤ n ≤ 2⋅10⁵，1 ≤ x ≤ 10⁹）——数组长度和操作中使用的整数；
• 第二行包含 n 个整数 a₁, a₂, ..., aₙ（0 ≤ aᵢ ≤ 10⁹）——表示数组 a。

题目保证所有测试用例中 n 的总和不超过 2⋅10⁵。

输出格式

对于每个测试用例，输出一行一个整数，表示通过最优操作后，数组 a 的最大 MEX 值。

示例

输入

3
6 3
0 3 2 1 5 2
6 2
1 3 4 1 0 2
4 5
2 5 10 3

输出

4
6
0

说明

• 第一个测试用例中，原始数组 a 的 MEX 就是 4，无需任何操作，已是最大。
• 第二个测试用例中，原始 MEX 是 5；我们可以对 a₁ 执行两次操作变成 a₁=5，最终数组变为 [5, 3, 4, 1, 0, 2]，MEX 为 6，是最大。
• 第三个测试用例中，数组中没有 0，因此 MEX 是 0，无需操作。