题目描述

憨憨的木厂有 $n$ 根原木，现在想把这些木头切割成 $k$ 段长度均为 $x$ 的小段木头（木头有可能有剩余）。为了加大对原木的利用率，我们想要使切出来的小段木头的长度尽可能的大（可能有剩余的木头）。例如有 $1$ 根原木，长 $11$ cm。要切割成 $3$ 段，那么 $x$ 最大为 $3$（多出来的 $2$ cm 就不要了）。

木头长度的单位是 cm，原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。

现在请你帮木厂求出 $x$ 的最大值。

输入格式

第一行包含一个整数 $T\ (1 ≤ T ≤ 2*10^5)$，表示测试用例的数量。

每组样例格式如下：

• 第一行有两个整数，$n$ 和 $k$ ($1\leq n,k\leq10^6$)，分别表示原木的数量和需要切割成几段。
• 第二行有 $n$ 个整数，表示原木的长度即 $a_i$ ($1\leq a_i\leq10^9$)。

输出格式

输出共一行。输出一个整数，即 $x$ 的最大值。

如果 $1$ cm 都切不出来，输出 0。

1
3 7
232
124
456

114