Tỷ lệ vàng trong nhiếp ảnh – Vòng xoắn ốc được phát triển từ các ô vuông có độ dài là một số Fibonacci. Khi đặt các hình vuông vào một khung hình, đường cung từ góc đối diện sẽ có dạng tương tự đường xoắn ốc. Mô hình này được thể hiện ở mọi vật trong tự nhiên. Đường cong xuyên qua khung hình sẽ hướng mắt người nhìn xung quanh bức ảnh.

Bạn Lam Phương đang đi chụp hình phong cảnh ở Tân An. Bỗng bạn Minh Thư chạy lại hỏi thăm chiếc máy ảnh vì máy ảnh bạn Lam Phương khá là xịn xò và hầm hố. Bạn thắc mắc chiếc máy ảnh to thế kia thì cho ra chất lượng ảnh là bao nhiêu đơn vị chiều rộng. Bạn Lam Phương lại muốn "flex" trình độ toán học của mình bằng cách không trả lời thẳng vấn đề mà gợi ý bạn Minh Thư rằng nếu Lam Phương chụp một bức ảnh có tỉ lệ vàng thì độ rộng bức ảnh là cạnh của hình vuông thứ ~N~ của hình xoắn ốc tỉ lệ vàng. Để tăng độ flex cho bản thân, kết quả Lam Phương đưa ra đó là cạnh mang giá trị lẻ hay chẵn thứ ~N~ của hình xoắn ốc tỉ lệ vàng.

Dữ liệu vào

• Dòng đầu tiên là số nguyên dương ~T~ ~(T \le 10)~ là số bộ test.
• T dòng tiếp theo, mỗi dòng gồm một số nguyên ~K \in \{0; 1\}~ và số ~N~ ~(1 \le N \le 10^{12})~.

Kết quả ra

• Gồm T dòng

  • Nếu ~K=0~ thì xuất ra cạnh mang giá trị lẻ thứ ~N~ của hình xoắn ốc tỉ lệ vàng.
  • Nếu ~K=1~ thì xuất ra cạnh mang giá trị chẵn thứ ~N~ của hình xoắn ốc tỉ lệ vàng.

  Lưu ý: Kết quả là một số nguyên dương chia lấy phần dư cho 27022007. Ảnh chụp có kích thước là một hình chữ nhật hoặc hình vuông.

Ví dụ

Dữ liệu vào

3
0 3
1 2
1 1

Kết quả ra

3
8
2

Giới hạn

• Có ~20~ tests có ~N \le 10^8~ , ~T \le 10~.
• ~10~ tests còn lại không ràng buộc gì thêm.