Nằm trong lòng công nghiệp công nghệ sôi động, VNG đã khẳng định vị thế là một trong những công ty hàng đầu tại Việt Nam. Với cam kết xây dựng một môi trường làm việc tuyệt vời, VNG không chỉ chú trọng vào sự phát triển chuyên môn mà còn đặc biệt quan tâm đến sự cân bằng giữa công việc và cuộc sống cá nhân của nhân viên.

Để nâng cao sự hài lòng và năng suất của nhân viên, VNG thường xuyên tổ chức các hoạt động thú vị và thử thách, như những câu đố và trò chơi logic. Một trong những thử thách nổi bật mà công ty đưa ra là "Cái cân Hà Nội"  – một trò chơi biến thể từ trò chơi Tháp Hà Nội.

Cái cân Hà Nội là một chiếc cân đĩa. Mỗi bên cân có một cái cọc, và ngoài ra có một cái cọc phụ nữa ở ngoài. Ban đầu, có một quả tạ với khối lượng ~s~ gram nằm ở cân phía bên phải. Cọc ở cân phía bên trái có chứa ~n~ đĩa tạ, lần lượt có khối lượng là ~2^0, 2^1, 2^2, \ldots, 2^{n - 1}~ gram theo thứ tự từ trên xuống dưới.

Được phép thực hiện thao tác sau không hoặc nhiều lần:

• Chọn một cọc ~A~ đang có ít nhất một đĩa tạ.

• Gọi quả cân trên cùng ở cọc ~A~ là ~x~.

• Chọn một cọc ~B~ khác cọc ~A~ sao cho cọc ~B~ không chứa đĩa tạ nào có khối lượng nhỏ hơn đĩa tạ ~x~.

• Di chuyển ~x~ từ cọc ~A~ sang cọc ~B~. Lúc này đĩa tạ trên cùng cọc ~B~ sẽ là ~x~.

Hãy tìm số lần di chuyển ít nhất sao cho đến cuối cùng:

• Hai bên cân của cái cân Hà Nội cân bằng, và

• mọi đĩa tạ đều nằm ở hai cọc trên cái cân Hà Nội.

Nếu không tồn tại cách di chuyển thỏa mãn, hãy chỉ ra điều đó.

Input

Đầu vào gồm nhiều bộ dữ liệu. Dòng đầu tiên của đầu vào chứa số nguyên ~t~ (~1 \le t \le 10\,000~) – số lượng bộ dữ liệu. Mô tả của mỗi bộ dữ liệu như sau.

Dòng đầu tiên và duy nhất của mỗi bộ dữ liệu gồm hai số nguyên ~s~ và ~n~ (~1 \le s \le 10^{18}~, ~1 \le n \le 60~) – khối lượng quả cân ở đĩa bên phải tính theo gram, và số lượng đĩa tạ nằm trên cọc ở đĩa cân bên trái.

Output

Với mỗi bộ dữ liệu, nếu như không tồn tại cách di chuyển làm cái cân Hà Nội cân bằng, hãy in ra ~-1~. Ngược lại hãy in ra một số nguyên duy nhất là số lần di chuyển ít nhất sao cho hai bên cân của cái cân Hà Nội cân bằng và mọi đĩa tạ đều nằm ở hai cọc trên cái cân Hà Nội.

Scoring

Sample Input 1

5
1 2
3 2
4 2
1 3
3 3

Sample Output 1

1
0
-1
3
3

Notes

Dưới đây là minh họa cho ví dụ đầu tiên:

Ở ví dụ thứ hai, ở bên trái bao gồm đĩa tạ có khối lượng lần lượt là ~2^0~ và ~2^1~ gram, còn bên phải có quả cân có khối lượng ~3~ gram. Như vậy cái cân Hà Nội đã cân bằng, và ta không cần phải di chuyển tạ.

Ở ví dụ thứ ba, ở bên trái bao gồm đĩa tạ có khối lượng lần lượt là ~2^0~ và ~2^1~ gram, tổng cộng là ~3~ gram. Còn ở bên phải có quả cân có khối lượng ~4~ gram. Bên trái nhẹ hơn bên phải, do đó nếu ta di chuyển tạ thì không thể tăng được khối lượng ở đĩa cân bên trái. Vì vậy không có cách di chuyển hợp lệ.

Dưới đây là minh họa cho ví dụ thứ tư:

Dưới đây là minh họa cho ví dụ thứ năm: