I. Drink Distribution
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Abdelaleem has $$$n$$$ different drinks, each consisting of $$$a_i$$$ liters. He has $$$m$$$ friends coming to visit him on Eid, and he wants each friend to have an equal amount of the same drink, so he cannot serve the same drink in cups of different sizes and he must serve to all friends.

At the same time, he does not want to have a small quantity of juice left in the pitcher (strictly less than $$$k$$$). Therefore, he decided to divide each type of juice among them so that he could either serve the entire quantity to them and nothing remains, or serve them such that a quantity greater than or equal to $$$k$$$ remains. He can choose to not serve them at all.

Can you tell me what is the maximum quantity he can offer for each one of them?

Input

The first line contains an integer $$$T$$$ – the number of test cases.

For each test case:

The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \leq n \leq 5 \times 10^5$$$)($$$1 \leq m,k \leq 10^9$$$) - the number of different drinks Abdelaleem has, and the number of friends they visit Abdelaleem, and the minimum allowable quantity of remaining liters, respectively.

The second line contains $$$n$$$ integers $$$a_1,a_2,…,a_n$$$ ($$$1 \leq a_i \leq 10^9$$$), the quantity of each drink.

Output

For each test case, the output maximum quantity he can offer for each one of them.

Example
Input
1
4 6 2
1 18 10 25
Output
7
Note

In the first testcase :

Abdelaleem will leave the first juice because it cannot be divided in a way that satisfies any of the conditions.

For the second juice, he will give each person $$$3$$$ units (nothing will be left in the bottle).

The third juice will give each person one unit ($$$4$$$ units will remain in the bottle, which is more than the required $$$k=2$$$ units to remain).

The last juice will give each person $$$3$$$ units, leaving $$$7$$$ units in the bottle that cannot be divided altogether or further in a way that leaves more than $$$k=2$$$ units.