Với một số nguyên dương \(x\), ta gọi \(Next(x)\) là số nguyên dương nhỏ nhất lớn hơn \(x\) nhưng có cùng số lượng bit \(1\) với \(x\) khi biểu diễn trong dạng nhị phân.

Ví dụ: \(Next(1) = 2; Next(6) = 9\).

Kí hiệu: \(Next^k(x) = Next(Next(...(Next(x))))\) (có tổng cộng \(k\) lần thực hiện hàm trong dấu ..., ví dụ \(Next^3(x) = Next(Next(Next(x)))\)).

Yêu cầu: Cho số nguyên dương \(x\) (\(x \le 10^{15}\)) và số nguyên dương \(k\), hãy tìm \(Next^k(x)\), nếu giá trị này vượt quá \(10^{15}\) thì đưa ra giá trị \(-1\).

Input

• Dòng đầu là số \(t\).
• \(t\) dòng sau, mỗi dòng chứa hai số nguyên \(x\) và \(k\).

Output

• Gồm \(t\) dòng, mỗi dòng là kết quả tương ứng với dữ liệu vào.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(k \le 10^2; t \le 10\).
• Subtask \(2\) (\(50\%\) số điểm): \(k \le 10^{15}; t \le 1000\).

Example

2
1 2
6 1

4
9