There are $$N$$ people standing in a row with some \(count_i\) $$(1 \le i \le 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 ≤10^3\)
\(1 ≤ N, M ≤10^5\)
\(0 ≤ Count_i ≤10^5\)
Sum of $$N$$ over all test cases \(\le10^7\)