CF2021B Maximize Mex

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 $ ( $ 1 \leq i \leq n $ ). 2. Increase $ a_i $ by $ x $ , in other words $ a_i := a_i + x $ . Find the maximum value of the $ \operatorname{MEX} $ of $ a $ if you perform the operations optimally. The $ \operatorname{MEX} $ (minimum excluded value) of an array is the smallest non-negative integer that is not in the array. For example: - The $ \operatorname{MEX} $ of $ [2,2,1] $ is $ 0 $ because $ 0 $ is not in the array. - The $ \operatorname{MEX} $ of $ [3,1,0,1] $ is $ 2 $ because $ 0 $ and $ 1 $ are in the array but $ 2 $ is not. - The $ \operatorname{MEX} $ of $ [0,3,1,2] $ is $ 4 $ because $ 0 $ , $ 1 $ , $ 2 $ and $ 3 $ are in the array but $ 4 $ is not.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 5000 $ ). The description of the test cases follows. The first line of each test case contains two integers $ n $ and $ x $ ( $ 1 \le n \le 2 \cdot 10^5 $ ; $ 1 \le x \le 10^9 $ ) — the length of the array and the integer to be used in the operation. The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le 10^9 $ ) — the given array. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

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

In the first test case, the $ \operatorname{MEX} $ of $ a $ is $ 4 $ without performing any operations, which is the maximum. In the second test case, the $ \operatorname{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 $ \operatorname{MEX} $ of $ a $ will become $ 6 $ , which is the maximum. In the third test case, the $ \operatorname{MEX} $ of $ a $ is $ 0 $ without performing any operations, which is the maximum.