题目描述

小红给了小明 $n$ 个糖果盒！每个糖果盒里面都有 $a_i$ 颗糖果。慷慨善良的小明现在要将这些糖果分给他的 $m$ 个同班同学！

为了公平起见，每个同学分到的糖果数量要都一样。同时，由于小明的算数不太好，每个同学分到的糖果必须只来自于同一个糖果盒，不能是多个糖果盒里的糖果凑出来的。现在小明想知道，每个同学最多可以拿到多少糖果。

注：害怕蛀牙的小明自己不需要糖果。

输入格式

输入文件第一行为一个整数 $T$，表示数据的组数。

接下来每组数据第一行包含两个正整数 $n, m$，含义见题目描述。

每组数据第二行包含 $n$ 个正整数 $a_i$，表示糖果盒里糖果的数量。

输出格式

输出共 $T$ 行，每行一个正整数，其中第 $i$ 行表示对于第 $i$ 组数据的答案。

样例数据

1
13 20
13 53 96 86 75 74 35 96 26 12 39 50 38

26

大样例

P157001.in/P157001.out

P157002.in/P157002.out

P157003.in/P157003.out

P157004.in/P157004.out

P157005.in/P157005.out

数据范围

对于 $20\%$ 的数据，满足 $1 \leq T \leq 5, 1 \leq \sum{n} \leq 20, 1 \leq a_i \leq 100$

对于 $40\%$ 的数据，满足 $1 \leq T \leq 20, 1 \leq \sum{n} \leq 5000, 1 \leq a_i \leq 10^6$

对于 $100\%$ 的数据，满足 $1 \leq T \leq 100, 1 \leq \sum{n} \leq 10^6, 1 \leq a_i \leq 2 \times 10^9$