Nhà máy Binary có một loạt các công việc được sắp xếp trên một cây nhị phân hoàn chỉnh có độ cao là h. Có w công nhân, mỗi công nhân trong một giờ chỉ thực hiện được 1 công việc từ gốc của cây nhị phân đó. Tại thời điểm đầu tiên chỉ có sẵn một công việc tại gốc của cây, do đó chỉ có 1 công nhân có việc để làm. Tại các thời điểm tiếp theo các công nhân sẽ lần lượt tham gia giải quyết các công việc có sẵn còn lại trên cây nhị phân. Hãy tính toán thời gian ngắn nhất để các công nhân hoàn thành hết công việc trên cây này.

Đầu vào

Dòng đầu tiên là một số \(t\) \((1 \leq t \leq 5 * 10^5 )\) là số lượng test case. Một \(t\) dòng tiếp theo bao gồm 2 số \(h\) \(( 1 \leq h \leq 50)\) là độ cao của cây nhị phân và \(w ( 1 \leq w \leq 10^4)\) là số lượng công nhân.

Đầu ra

Đầu ra của mỗi test case là một số nguyên duy nhất là thời gian nhỏ nhất để các công nhân hoàn thành cây nhị phân

Ví dụ

Input

3
3 1
3 2
10 6

Output

7
4
173

Giải thích

Tại ví dụ 2, ban đầu chỉ thực hiện 1 công nhân làm việc, những lần sau thì cả 2 công nhân cùng làm việc.