Description

Syd凭借各种各样的原因，在新生中有了超高的人气，于是她决定开淘宝店捞一波钱。（喵喵喵？） 她的淘宝店里有各种各样的砖头。简单的说，一共有n种不同的砖头，每块砖头售价ai。

为了迎接双十一，syd决定调整一下店里砖头的价格，让每种砖头都卖一样的价钱，让这些砖头看起来更实惠。

但是，syd又不想亏钱，毕竟砖头的成本也是很贵的！！所以她调整后的价格的和要不小于初始价格的总和。这意味着，如果syd以新价格出售所有n种砖头，syd甚至还能赚的更多。（至少赚的不会少）

另一方面，syd又不想因为砖头太贵卖不出去，因此她必须选择可以选择所有价格中的最低价格。

你能编程帮帮syd给所有砖头定一个最合适价格吗？如果你能做到，syd一定会奖励你一块最棒的砖头的！！

Input

输入的第一行包含一个整数q（1≤q≤100）代表q个查询数。

每个查询的第一行包含一个整数n（1≤n≤100）商品数。 查询的第二行包含n个整数a1，a2，…，an（1≤ai≤1e7），其中ai是第i个商品的价格。

Output

对于每个查询，输出一个整数，代表你帮syd定的每块砖头的价格

Samples

3
5
1 2 3 4 5
3
1 2 2
4
1 1 1 1

3
2
1