Hyouka

Hotaro Oreki is a pragmatic boy who lives by "If I don't have to do something, I won't, but if I have to, I'll do it quickly."

Hotaro lives in Japan and Japan is known around the world for its cherry blossom festivals, also known as "Hanami".
Many kids will join in the upcoming Hanami festival. To increase their happiness festival committee decided to gift them
colorful balls to play with. But distributing balls among large number
of kids and keeping them satisfied is very difficult job to do. But the good thing is that the festival committee know the
number of kids coming will be some integer number K.
Hotaro is given this hard task to solve on behalf of the festival committee.

There will be N boxes and each box will contain some amount of balls of same type.
Hotaro needs to find the number of ball(s) for these K kids so that,

• Each kid gets equal number of balls
• Each kid gets only one type of balls, not balls of different types
• Each kid gets at least one ball each for sure otherwise they will be sad
• Amount of balls each kid gets should be maximum
• Amount of balls that are left in the boxes should be minimum

Do you agree with Hotaro's life motto? Can you prove yourself pragmatic enough by quickly finding the number Hotaro came with?

Input

The first line of the input will contain a single integer T(1≤T≤15) that denotes the number of test cases.

For each test case, the first line will contain 2 integers N and K (1≤N,K≤100,000) where N denotes the number of boxes and K denotes the number of kids coming in Hanami festival.
Next line will contain N space-separated integers a1, a2,a3,...., aN, where, ai(1<=ai<=1000000000) denotes the the number of balls in each boxes from i'th.
Sum of all $ \sum_{i=1}^{N} a_{i} $ will always be greater than or equal to the number of kids.

Output

For each case, print the number Hotaro came with.

Sample

3
3 5
3 1 1
3 2
5 1 6
1 4
12

1
5
3