Mario is playing a game where he has to reach a rock by jumping over n (1 <= n <= 10^5) other rocks. Each rock i has a coin Ai (1 <= i <= n) on them. Mario can either take the coin or he can skip it. Taking a coin will add its value to his score.
Mario can take Ai if, all Aj (1 <= j <= n) such that Ai = Aj and ∑Aj (summation of all Aj) is divisible by k (1 <= k <= 10^3).
After jumping over all the rocks serially, Mario has to maximize his score.
Given n, k and coins value on each of the n rocks, determine the maximum score Mario can get.
Input
First line of input is a number T (1 <= T <= 10). Each of the next T lines has 2 inputs n, k. Next line will have n inputs for Ai (1 <= Ai <= 10^18).
Output
For each case there should one number as output. The maximum value. Since the value can be very large, you have to print the value modulo 2^64.
Sample
| Input | Output |
|---|---|
1 5 7 14 8 21 14 1 | 49 |
