 Prepare
 Interview Preparation Kit
 Search
 Maximum Subarray Sum
Maximum Subarray Sum
Maximum Subarray Sum
 Prepare
 Interview Preparation Kit
 Search
 Maximum Subarray Sum
We define the following:
 A subarray of array of length is a contiguous segment from through where .
 The sum of an array is the sum of its elements.
Given an element array of integers, , and an integer, , determine the maximum value of the sum of any of its subarrays modulo .
Example
The following table lists all subarrays and their moduli:
sum %2
[1] 1 1
[2] 2 0
[3] 3 1
[1,2] 3 1
[2,3] 5 1
[1,2,3] 6 0
The maximum modulus is .
Function Description
Complete the maximumSum function in the editor below.
maximumSum has the following parameter(s):
 long a[n]: the array to analyze
 long m: the modulo divisor
Returns
 long: the maximum (subarray sum modulo )
Input Format
The first line contains an integer , the number of queries to perform.
The next pairs of lines are as follows:
 The first line contains two spaceseparated integers and (long), the length of and the modulo divisor.
 The second line contains spaceseparated long integers .
Constraints
 the sum of over all test cases
Sample Input
STDIN Function   1 q = 1 5 7 a[] size n = 5, m = 7 3 3 9 9 5
Sample Output
6
Explanation
The subarrays of array and their respective sums modulo are ranked in order of length and sum in the following list:
 and
and



The maximum value for for any subarray is .