CF1374D Zero Remainder Array

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.

The first line of the input contains one integer $ t $ ( $ 1 \le t \le 2 \cdot 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 \le n \le 2 \cdot 10^5; 1 \le k \le 10^9 $ ) — the length of $ a $ and the required divisior. The second line of the test case contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^9 $ ), where $ a_i $ is the $ i $ -th element of $ a $ . It is guaranteed that the sum of $ n $ does not exceed $ 2 \cdot 10^5 $ ( $ \sum n \le 2 \cdot 10^5 $ ).

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

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.