题目内容

在一个能量实验中，科学家收集了若干能量晶体，按获取顺序排成一列，每个晶体都有一个正整数能量值。

现在需要从中选取一部分晶体，为实验装置供能。装置有一个参数 $M$，称为调制基数。选取时，必须保持晶体在原序列中的先后次序，但可以不连续。选取的晶体个数至少为 $1$，这种选取方式称为原序列的一个非空子列。

将选中晶体的能量值相加，得到一个总和，然后用这个总和除以 $M$，以得到的余数作为有效输出。你的任务是：给定能量值序列和调制基数 $M$，计算通过选择一个非空子列，能够得到的最大余数。

数据范围

测试数据的组数不超过 2×10^4。对于每组数据，序列的长度 $n$ 不超过 2×10^4，调制基数 $M$ 满足 $1 \le M \le n$。序列中的能量值均为不超过 10^9 的正整数。所有测试数据中 $n$ 的总和不超过 6×10^4。

输入描述

第一行包含一个整数 $T$，表示测试数据的组数。 接下来有 $T$ 组数据，每组数据占两行： 第一行包含两个整数 $n$ 和 $M$，表示能量值序列的长度和调制基数。 第二行包含 $n$ 个整数，表示序列中每个晶体的能量值。

输出描述

对于每组测试数据，输出一行一个整数，表示能够获得的最大余数。

样例1

输入

2
4 4
3 1 4 2
3 5
9 6 3

输出

3
4

说明

共两组测试数据。

第一组：序列为 3, 1, 4, 2，调制基数 $M = 4$。考虑若干非空子列的和：全选 $3+1+4+2 = 10$，$10 \bmod 4 = 2$；选取 $3+4 = 7$，$7 \bmod 4 = 3$；选取 $1+4+2 = 7$，余数同样为 3；其余子列（如只选 3、只选 2 等）余数均不超过 3。因此该组能获得的最大余数为 3。

第二组：序列为 9, 6, 3，$M = 5$。只选 9 时，$9 \bmod 5 = 4$；只选 6 时余 1；只选 3 时余 3；选 6+3 = 9，余 4；选 9+6 = 15，余 0；选 9+3 = 12，余 2；全选 9+6+3 = 18，余 3。因此最大余数为 4。

样例2

输入

1
3 1
7 8 9

输出

0

说明

仅有一组数据：序列为 7, 8, 9，调制基数 $M = 1$。任何整数除以 $1$ 的余数均为 0，因此任意非空子列的和模 $1$ 的结果总是 0。能获得的最大余数为 0，这也是 $M=1$ 时唯一可能的答案。

样例3

输入

1
1 6
10

输出

4

说明

仅有一组数据：序列中只有一个能量值 10，调制基数 $M = 6$。非空子列只能选择该元素本身，$10 \bmod 6 = 4$，因此最大余数为 4。该样例展示了 $n=1$ 的边界情况。