解题思路
设选择出的非空子序列元素和为 S，目标是最大化 Smodk。
由于子序列只要求保持相对顺序，但求和与顺序无关，所以本题本质上就是：
从数组中选一个非空子集，使得其元素和对 k 取模尽量大。
状态设计
题目内容
给定一个长度为 n的整数数组 {a1,a2,…,an} 和一个正整数 k。请选择一个非空子序列（不要求连续），将其元素之和对k 取模，得到一个位于[0,k)的整数。请计算这个值的最大可能结果。
非空子序列指从原数组中删除任意个（可以为零，但不能全部）元素后得到的新序列，保持原相对顺序，但不要求连续。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≤T≤2×104)表示数据组数。此后对每组数据：
- 第一行输入两个整数 n,k(1≤k≤n≤2×104)；
- 第二行输入n个整数a1,a2,…,an(1≤ai≤109)。
除此之外，保证单个测试文件的 n之和不超过 6×104。
输出描述
对于每一组测试数据，新起一行输出一个整数，表示选择某个非空子序列后，其元素之和对 k 取模所得的最大值。
样例1
输入
3
5 5
3 8 2 6 4
5 5
5 10 15 20 5
3 4
输出
4
0
3
说明
对于第1组：例如选择子序列{4}，其和为4，对5取模为4，这是可能的最大值(也可选择{3,6}，其和为9，对5取模为4)。
对于第2组：所有元素均为5的倍数，任意非空子序列的和也是5的倍数，最大取模结果为0。
对于第3组：选择{3}或{1,2}的和对4取模均为3，为最大值。
