The Association of Counterintelligence Measures (ACM) is at it again. This time they're trying to generate some random numbers. After generating many sequences of 'random' numbers they began to wonder if the sequences are truly random. Again, your boss has a wonderful idea (not really): given some value K, a truly random sequence will have K consecutive numbers that sum to a very large value. If the largest K consecutive sum is very big, then the sequence is indeed truly random.

Input

The input will begin with a line containing a single positive integer, t, representing the number of test cases to process. Each test case will begin with two integers N and K (1 ≤ K ≤ N ≤ 1,000,000); N is the amount of random numbers that were generated and K is as described in the problem statement. The second line of each test case will contain N space separated positive integers which will be no greater than 1,000.

Output

For each test case print the maximum sum we can achieve from summing K consecutive numbers.

Example

Input:
2
5 3
1 5 3 2 5
10 4
12 43 49 20 20 3 0 19 20 30

Output:
10
132