Gluttons

Every year Megabyteland hosts The Great Gluttony Festival. According to tradition, during the first day of the festival all participants eat cookies nonstop for 24 hours (with not even a fraction of a second's break!). As soon as a glutton has finished eating one cookie, he immediately stars to eat the next one (this does not apply only to the situation at the end of the day, when the participant is not allowed to start eating a cookie if he knows that he cannot finish eating it before the end of the day). Another important part of the tradition is that each glutton eats a single cookie at his very own constant characteristic pace.

For the coming festival, the organizers have invited only those gluttons who have already participated in the previous editions. This means that the pace of each glutton is already known (they don't really like to change their natural pace). Based on this data, the organizers of the festival want to determine how many cookies they need to buy. However, the cookies in the shop are sold in boxes of fixed size, thus they may have to buy more cookies than the number that is going to be eaten.

Your task is to establish the number of boxes with cookies that are needed to carry out the competition. The number of participants, along with the pace of each of them (given in seconds needed to eat a single cookie) will be given.

Input

The first line of input contains the number of test cases t. Each test case has the following form: two numbers N and M, separated by a space, in the first line (1 ≤ N ≤ 10000, 1 ≤ M ≤ 1000000000). The first number N is the number of invited gluttons and the second number M is the numbers of cookies in the box. Each line of the next N lines contains a single integer number, representing the pace of the glutton. The pace of the glutton is expressed as the number of seconds (not greater than 100000) needed to eat a single cookie.

Output

For each test case you need to write exactly one integer denoting the number of boxes which have to be bought by the organizers to carry out the contest. Answers for distinct test cases should be written in separate lines.

Example

Input:
2
2 10
3600
1800
3 356
123
32999
10101

Output:
8
2

Please log in to submit your solution.