Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

B. Maximize Mex
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array a of n positive integers and an integer x. You can do the following two-step operation any (possibly zero) number of times:

  1. Choose an index i (1in).
  2. Increase ai by x, in other words ai:=ai+x.

Find the maximum value of the MEX of a if you perform the operations optimally.

The MEX (minimum excluded value) of an array is the smallest non-negative integer that is not in the array. For example:

  • The MEX of [2,2,1] is 0 because 0 is not in the array.
  • The MEX of [3,1,0,1] is 2 because 0 and 1 are in the array but 2 is not.
  • The MEX of [0,3,1,2] is 4 because 0, 1, 2 and 3 are in the array but 4 is not.
Input

Each test contains multiple test cases. The first line contains the number of test cases t (1t5000). The description of the test cases follows.

The first line of each test case contains two integers n and x (1n2105; 1x109) — the length of the array and the integer to be used in the operation.

The second line of each test case contains n integers a1,a2,,an (0ai109) — the given array.

It is guaranteed that the sum of n over all test cases does not exceed 2105.

Output

For each test case, output a single integer: the maximum MEX of a if you perform the operations optimally.

Example
Input
3
6 3
0 3 2 1 5 2
6 2
1 3 4 1 0 2
4 5
2 5 10 3
Output
4
6
0
Note

In the first test case, the MEX of a is 4 without performing any operations, which is the maximum.

In the second test case, the MEX of a is 5 without performing any operations. If we perform two operations both with i=1, we will have the array a=[5,3,4,1,0,2]. Then, the MEX of a will become 6, which is the maximum.

In the third test case, the MEX of a is 0 without performing any operations, which is the maximum.