There are N people standing in a row with some counti (1≤i≤N) number of chocolates in their hands. You have to select a range of people and take all their chocolates with the condition that you should be able to distribute those chocolates equally among M boxes.
Write a program to determine the maximum number of chocolates that can be placed in a box.
Input format
- First line: T (number of test cases)
- First line in each test case: Two space-separated integers N and M
- Second line in each test case: N space-separated integers (denoting the number of chocolates)
Output format
For each test case, print the maximum number of chocolates that can be placed in a box.
Constraints
1≤T≤103
1≤N,M≤105
0≤Counti≤105
Sum of N over all test cases ≤107
In first case, you can choose the range [1 , 5] as 1+2+3 + 4 + 5 = 20 , each box will have 5 chocolates.
In second case, you can choose the range [3 , 5] as 3 + 4 + 5 = 12 , each box will have 3 chocolates.
In third case, there is no way to choose any range such that 8 boxes can be filled equally.
