#CF2021B. 最大化 MEX

最大化 MEX

B. 最大化 MEX
每次测试时间限制:11
内存限制:256256 兆字节

给定一个由 nn正整数组成的数组 aa 和一个整数 xx
你可以执行以下两步操作任意次(包括零次):

  1. 选择一个下标 ii1in1 \le i \le n)。
  2. aia_i 增加 xx,即 ai:=ai+xa_i := a_i + x

如果以最优方式执行操作,求数组 aaMEX 的最大可能值。

MEX(最小排除值) 是指不在数组中的最小非负整数。例如:

  • [2,2,1][2,2,1] 的 MEX 是 00,因为 00 不在数组中。
  • [3,1,0,1][3,1,0,1] 的 MEX 是 22,因为 0011 都在数组中,但 22 不在。
  • [0,3,1,2][0,3,1,2] 的 MEX 是 44,因为 0,1,2,30,1,2,3 都在数组中,但 44 不在。

输入格式
每个测试包含多个测试用例。第一行包含测试用例数 tt1t50001 \le t \le 5000)。
每个测试用例的第一行包含两个整数 nnxx1n21051 \le n \le 2 \cdot 10^51x1091 \le x \le 10^9)——数组长度和操作中的整数 xx
每个测试用例的第二行包含 nn 个整数 a1,a2,,ana_1, a_2, \dots, a_n0ai1090 \le a_i \le 10^9)——给定的数组。
保证所有测试用例的 nn 之和不超过 21052 \cdot 10^5

输出格式
对于每个测试用例,输出一个整数:以最优方式执行操作后,数组 aa 的最大可能 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

说明

  • 第一个测试用例:不进行任何操作时,MEX 已经是 44,这是最大值。
  • 第二个测试用例:不进行操作时 MEX 为 55。如果对 i=1i=1 执行两次操作,数组变为 [5,3,4,1,0,2][5,3,4,1,0,2],此时 MEX 变为 66,这是最大值。
  • 第三个测试用例:不进行操作时 MEX 已经是 00,这是最大值。