G. Greatest Math Problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Vaz Lime is one of the most renowned calculus teachers in the world and really enjoys teaching class. So much so, that even though his class is the one right before lunch, he won't allow the hungry students to go (not even 1 minute before the bell!).

Fortunately, Romariz is one of the best math students of the class, and one day confidently challenges the teacher to a math duel. Vaz Lime determines that he will give Romariz a series of questions that, if answered correctly in less than two seconds, will allow the students that day to go to lunch earlier.

Romariz is given several test cases containing an array of length $$$n$$$ and an integer $$$k$$$ related to that array. For each test case, he needs to find the largest value of a positive integer $$$x$$$, such that $$$\sqrt{\lfloor \frac{a_1}{x} \rfloor + \lfloor \frac{a_2}{x} \rfloor + ... + \lfloor \frac{a_n}{x} \rfloor} \geq k$$$

Input

The first line of the input contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — the amount of test cases that Vaz Lime gives to Romariz.

The first line of each test case contains two integers $$$n$$$, $$$k$$$ $$$(1 \leq n \leq 10^6)$$$, $$$(1 \leq k \leq 10^9)$$$ — the amount of elements in the array and the associated integer.

The second line of each test case contains $$$n$$$ integers $$$(a_1, a_2, ..., a_n)$$$ $$$(1 \leq a_i \leq 10^{9})$$$ — the elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^6$$$.

Output

For each test case, output the maximum value of a positive integer $$$x$$$ that satisfies the equation. If no such number exists, print out -1.

Examples
Input
1
4 5
123 94 21 2
Output
9
Input
3
5 10
39 281 2 3 2
4 7
2 8 34 1223
7 5
9 4 28 9 3 12 95
Output
3
25
5