Cho một lưới hình chữ nhật gồm \(N\) hàng và \(M\) cột, mỗi ô có thể được gắn nhãn đen (Âm) hoặc trắng (Dương). Hai ô là láng giềng nếu chúng chung nhau một đoạn cạnh đơn vị. Lưới được gọi là hợp lệ nếu tất cả các ô đen tạo thành một đường đi, và tất cả các ô trắng tạo thành một đường đi. Một đường đi là một tập hợp \(S\) các ô được định nghĩa như sau:

• Các ô tạo thành một phần kết nối. Từ mỗi ô trong \(S\), bạn có thể đến bất kỳ ô nào khác trong \(S\) bằng cách di chuyển giữa các ô láng giềng trong \(S\).
• Có đúng hai ô trong \(S\) có đúng một láng giềng trong \(S\). Đây là hai "đầu mút" của đường đi.
• Mọi ô khác trong \(S\) có đúng hai láng giềng trong \(S\).

Ví dụ, trong hình dưới đây, lưới đầu tiên là hợp lệ, trong khi lưới thứ hai thì không -- mặc dù các ô đen tạo thành một đường đi, nhưng các ô trắng thì không.

Cho \(N\) và \(M\), hãy tính số lượng lưới hợp lệ. Lưu ý rằng tính đối xứng không quan trọng -- miễn là hai lưới hợp lệ khác nhau ở một vị trí thì chúng được coi là khác nhau, ngay cả khi lưới này có thể được xoay hoặc lật để trở thành lưới kia.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào là một số nguyên duy nhất \(T\), số lượng bộ test. \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi một khoảng trắng: "\(N\) \(M\)", như định nghĩa ở trên.

Dữ liệu ra

Với mỗi bộ test, xuất một dòng có dạng "Case #\(x\): \(A\)", trong đó \(x\) là số thứ tự bộ test, bắt đầu từ 1, và \(A\) là số lượng lưới hợp lệ có kích thước đã cho.

Ràng buộc

• \(1 \le T \le 50\)

Phân nhóm

• Test set 1 (Visible): \(4 \le N, M \le 10\).
• Test set 2 (Hidden):
  • Trong 80% số bộ test, \(4 \le N, M \le 50\).
  • Trong 90% số bộ test, \(4 \le N, M \le 70\).
  • Trong tất cả các bộ test, \(4 \le N, M \le 100\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
4 4
4 6
5 5

Case #1: 24
Case #2: 44
Case #3: 48

Nguồn

Google Code Jam 2010, Chung kết thế giới, bài The Paths of Yin Yang.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.