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

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

Ký hiệu:NextK(𝑥) = Next(Next (… (Next(𝑥))))

Yêu cầu: Cho số nguyên dương 𝑥 (𝑥≤10^15) và số nguyên dương 𝑘, hãy tìm NextK(𝑥) 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 <= 1000);

 - t dòng sau, mỗi dòng chứa hai số nguyên 𝑥 và 𝑘

(k <= 10^15) .

Output:

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