Ngày xửa ngày xưa, có một tên sợ vợ tên là Pirate. Hắn sợ vợ nhất làng nhưng lại muốn ra oai trước mọi người. Thế là hắn bèn xây cho nhà mình một cái giếng. Mỗi lần vợ bị rượt chạy trối chết, hắn đều nhằm thẳng cái giếng rồi chạy vòng vòng quanh nó. Người ngoài nhìn vào thấy hai vợ chồng đang chạy quanh cái giếng, chẳng biết ai đang đuổi đánh ai cả, cứ tưởng tên này đang "dạy vợ". Muốn mình càng nổi tiếng hơn nữa, hắn quyết định là cái giếng của nhà mình phải thật là đặc biệt. Vậy là hắn bắt tay vào thiết kế...

Giếng nhà Pirate là một khối hình trụ tròn rỗng. Giếng gồm nhiều vòng, vòng này chồng lên vòng kia. Mỗi vòng được xây bằng các viên đá ong bằng nhau. Viên đá ở vòng trên phải được đặt thẳng hàng với viên đá ở vòng dưới làm cho khi nhìn ngang từ bên ngoài, cái giếng trong giống như một bảng hình chữ nhật gồm các ô vuông.

Mỗi viên đá ong có thể được sơn mặt ngoài bằng một trong hai màu: trắng hoặc đen. Sơn giếng xong rồi, Pirate bèn khắc lên đó một câu đố nhằm lưu danh thiên cổ. Câu đố như sau: "Có bao nhiêu cách sơn giếng khác nhau? Trong đó, có bao nhiêu cách để nhìn từ ngoài vào không thấy bất cứ hình vuông ~2 \times 2~ nào được sơn hoàn toàn bằng một màu?".

Hai cách sơn gọi là khác nhau nếu không thể "xoay" một số lần để cách này trùng với cách kia. Nếu hình dung cái giếng như một bảng hai chiều, phép "xoay" ở đây là việc dời cột bên trái nhất (cột ~1~) sang phía ngoài cùng bên phải.

Cái giếng đúng là tầm thường nhưng câu đố đúng là bất hủ đấy, các bạn thử giải xem!

Input

• Dòng thứ nhất là số nguyên ~T~ - số bộ test ~(1 \leq T \leq 15)~.

• ~T~ dòng tiếp theo: mỗi dòng gồm ~3~ số nguyên: ~K~ - loại câu hỏi; ~M~ - số vòng của giếng; và ~N~ - số viên đá trên mỗi vòng.

  • Nếu ~K = 1~, bạn phải trả lời câu hỏi có bao nhiêu cách sơn khác nhau ~(1 \leq M \leq 10^3, 1 \leq N \leq 20)~.
  • Nếu ~K = 2~, bạn phải trả lời câu hỏi trong tất cả các cách sơn khác nhau, có bao nhiêu cách mà không có hình vuông ~2 \times 2~ nào được sơn bằng một màu ~(1 \leq N \leq 8, 1 \leq M \times N \leq 64)~.

Output

Gồm ~T~ dòng: mỗi dòng là số cách sơn giếng ở test tương ứng.

Giới hạn

~40\%~ số test có ~1 \leq M \times N \leq 20~.

Sample Input

1
2 2 2

Sample Output

8

Note

Ta có ~8~ cách sơn như sau: (Giả sử màu đen là 'X', màu trắng là 'O')

XO  OO  XO  XX  OO  XO  OX  XX
OO  XO  XO  OO  XX  OX  XX  XO

Lưu ý rằng các cách sơn sau được xem là như nhau:

XO -> OX        OO -> OO
OO -> OO        XO -> OX

XO -> OX        XO -> OX
XO -> OX        OX -> XO

XX -> XX        XO -> OX
XO -> OX        XX -> XX