Có ~N~ bệnh nhân đến khám tại phòng khám. Giả sử rằng cứ sau ~X~ (phút) thì có một bệnh nhân mới đến phòng khám. Ngoài ra, bác sĩ sẽ chỉ dành ~10~ phút để khám cho mỗi bệnh nhân. Nhiệm vụ của bạn là tính toán thời gian (bằng phút) mà bệnh nhân cuối cùng cần phải chờ đến lượt mình được bác sĩ khám bệnh.

Input

Dòng đầu tiên của đầu vào chứa số nguyên ~T~ cho biết số bộ dữ liệu cần kiểm tra. Mỗi bộ dữ liệu gồm một dòng chứa hai số nguyên ~N~ và ~X~.

Output

Ứng với mỗi bộ dữ liệu đầu vào, chương trình của bạn cần in ra một dòng chứa số ~M~ là số phút mà bệnh nhân cuối cùng cần chờ bác sĩ tại phòng khám.

Constraints

• ~1 \le T \le 500; 1 \le N \le 100; 0 \le X \le 30~.

Sample Input

5
4 5
5 3
6 5
7 6
8 2

Sample Input

15
28
25
24
56

Mai thích đi dạo trong Công viên trung tâm thành phố. Nhưng cô ấy muốn kết hợp với việc đi bộ nhàm chán bằng việc nhặt các viên sỏi, vì vậy cô ấy bắt đầu thu nhặt các viên sỏi trong công viên.

Mỗi ngày, khi đi bộ, Mai chỉ mang theo hai cái túi. Cô ấy có thể bỏ nhiều nhất là ~k~ viên sỏi vào một túi. Có ~n~ loại sỏi khác nhau trong công viên, loại thứ ~i~ gồm ~w_i~ viên sỏi. Mai là người rất ngăn nắp, vì vậy cô ấy không bao giờ trộn các loại sỏi khác nhau trong cùng một túi. Như vậy, mỗi ngày đi bộ, cô ấy có thể nhặt về hai túi sỏi khác loại. Tuy nhiên, sỏi trong công viên khá nhiều và Mai không thể nhặt tất cả các viên sỏi trong công viên trong một lần đi, vì vậy cô ấy sẽ phải nhặt sỏi trong công viên trong một số ngày.

Hãy giúp Mai tính số ngày tối thiểu cần thiết để thu nhặt tất cả các viên sỏi trong Công viên, nhớ rằng Mai không thể bỏ các viên sỏi khác nhau trong cùng một túi.

Dữ liệu:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ (~1 \le n \le 10^{5}, 1 \le k \le 10^{9}~) tương ứng là số lượng các loại sỏi khác nhau và số lượng sỏi Mai có thể đặt trong một túi.
• Dòng thứ hai chứa ~n~ số nguyên ~w_1, w_2, ..., w_n~ (~1 \le w_ {i} \le 10^{4},i=1..n~) là số lượng sỏi mỗi loại.

Kết quả:

• Ghi ra một số nguyên duy nhất là số ngày tối thiểu mà Mai cần để nhặt hết tất cả các viên sỏi trong công viên.

Ví dụ:

Sample Input 1

3 2
2 3 4

Sample Output 1

3

Sample Input 2

5 4
3 1 8 9 7

Sample Output 2

5

Nhập vào ~N~ số nguyên và in ra số nguyên lớn thứ nhì trong số đó. Nếu các số bằng nhau thì coi như số lớn thứ nhì bằng số lớn nhất.

Dữ liệu:

• Dòng đầu chứa số nguyên ~N~;
• Dòng sau, chứa ~N~ số nguyên cách nhau một dấu cách.

Kết quả:

• In ra số nguyên lớn nhì trong số các số nguyên đã nhập.

Ràng buộc:

• ~2 \leq N \leq 10^6~;
• Các số nguyên có giá trị tuyệt đối không quá ~10^9~.

Ví dụ:

Sample Input

5
5 1 2 3 4

Sample Output

4

Bạn Cừu mới học môn Hóa học được biết rằng: Một phân tử nước ~H_2O~ gồm có hai nguyên tử Hydro và một nguyên tử Oxy. Hôm nay, bạn Cừu tự hỏi nếu như có số lượng Hydro và Oxy nhất định thì có thể có bao nhiêu phân tử nước. Em hãy lập trình tính số lượng phân tử nước tối đa mà bạn ấy có thể nhận được.

Biết rằng nếu mỗi nguyên tử ~O~ và ~H~ đã sử dụng liên kết với nhau thì không thể kết hợp với nguyên tử khác.

Dữ liệu:

• Một dòng duy nhất chứa một xâu ~S~ (độ dài không quá ~1000~ ký tự) chỉ gồm các ký tự ~H~ và ~O~.

Kết quả:

• Đưa ra một số nguyên là số lượng phân tử nước tối đa mà Cừu có thể nhận được.

Ví dụ:

Sample Input 1

HHOHHO

Sample Output 1

2

Sample Input 2

HHHHHHOOOO

Sample Output 2

3