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))))\)

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 \(-1\)

Dữ liệu vào

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

Dữ liệu ra

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

Intput 1

2
1 2
6 1

Output 1

4
9

Ràng buộc

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