你是附近一家小商店的店主和店员。您有 $$$n$$$ 商品,第 $$$i$$$ 商品需要花费 $$$a_i$$$ 硬币。
您厌倦了在客户询问时记住每种产品的价格,因此您决定简化您的生活。更准确地说,您决定为您拥有的所有 $$$n$$$ 商品设置相同的价格。
但是,您不想损失任何金钱,因此您希望选择的价格使得新价格的总和不小于初始价格的总和。这意味着,如果您以新价格出售所有 $$$n$$$ 商品,您将至少收到与以初始价格出售它们相同(或更多)的金额。
另一方面,您不想因为价格过高而失去客户,因此在您可以选择的所有价格中,您需要选择最低的价格。
因此,您需要找到所有 $$$n$$$ 商品的最低可能相等价格,因此,如果您以这个价格出售它们,您将至少收到与以初始价格出售它们相同(或更多)的金额。
您必须回答 $$$q$$$ 独立查询。
输入
输入的第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 100$$$) — 查询数。然后是 $$$q$$$ 查询。
查询的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100)$$$ — 商品数量。查询的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^7$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 商品的价格。
输出
对于每个查询,打印它的答案 - 所有 $$$n$$$ 商品的最低可能同等价格,因此如果您以这个价格出售它们,您将收到至少与您以初始价格出售它们相同(或更多)的金额。
示例
输入 #1
3 5 1 2 3 4 5 3 1 2 2 4 1 1 1 1
输出 #1
3 2 1