Zero Remainder Array

题意翻译

给定一个正整数 $k$。称一个长度为 $n$ 的正整数序列 $a_1,...,a_n$ 是**好的**当且仅当对于每个 $a_i$ 都有 $k$ 整除 $a_i$。 现在给定了这个数组 $a$。有一个变量 $x$，初始时为 $0$。将进行若干次操作，每次操作如下： - 选择一个 $i(1\leq i\leq n)$，然后令 $a_i\gets a_i+x$；或者什么都不做； - 令 $x\gets x+1$。 问至少多少次操作后能把 $a$ 变成**好的**。 注意有多组数据。 保证 数据组数 $\leq 2\times 10^4$，$1\leq n\leq 2\times 10^5,1\leq k,a_i\leq 10^9,\sum n\leq 2\times 10^5$。 **注意：你只可以给同一个数加一次 $x$。**

题目描述

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

输入输出样例

输入样例 #1

5
4 3
1 2 1 3
10 6
8 7 1 8 3 7 5 10 8 9
5 10
20 100 50 20 100500
10 25
24 24 24 24 24 24 24 24 24 24
8 8
1 2 3 4 5 6 7 8

输出样例 #1

6
18
0
227
8

说明

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.