Nhắc lại về phép XOR (kí hiệu ~\oplus~):

• ~0 \oplus 0 = 0~
• ~0 \oplus 1 = 1~
• ~1 \oplus 0 = 1~
• ~1 \oplus 1 = 0~

Phép $a \bmod b$ là phần dư của ~a~ khi chia cho ~b~.

Gấu nhờ bạn tìm số nguyên dương $x$ nhỏ thứ ~k~ mà ~x \oplus n = x \bmod n~

Dữ liệu vào

Dòng đầu tiên gồm số nguyên ~T~ ~(1 \leq T \leq 10^5)~ là số bộ test.

~T~ dòng sau mỗi dòng chứa hai số nguyên ~n, k~ ~(1 \leq n, k \leq 10^9)~.

Dữ liệu ra

Gồm ~T~ dòng là đáp án cho ~T~ bộ dữ liệu.

Nếu không đủ ~k~ số ~x~ thỏa mãn thì in ra ~-1~.

Ví dụ

Input

5
2 1
2 2
20 3
2 4
27092008 5

Output

2
3
22
-1
27092012

Note

Xét ~n = 2~: có ~x \in \{2, 3\}~ thỏa mãn.

Tính điểm

• Subtask 1 (30% số điểm): ~1 \leq n, k \leq 10000, 1 \leq T \leq 10~.
• Subtask 2 (70% số điểm): Không có ràng buộc gì thêm.