Đề bài

Trên một thảo nguyên nhỏ bé có một gia đình gồm ba anh em:
hai người anh trai là Nvutri và Andorea, cùng cô em gái Lola.

Cuộc sống gia đình khá giả, nhưng vì muốn các con tự lập, cha mẹ quyết định để ba anh em hằng ngày tự đi chăn một số bò (mỗi người tùy ý chọn số bò mình chăn).

Thảo nguyên là một cánh đồng chia thành M × N ô vuông.

• Mỗi con bò đứng trong một ô và mỗi ô chỉ chứa một con bò.
• Chỉ có một quy tắc duy nhất:
  
  • Không được để 4 con bò tạo thành một hình vuông 2×2.
  • Không được để 4 ô đất trống tạo thành một hình vuông 2×2.

Hai người anh mải chơi nên đã hối lộ kem để Lola phải chăn bò một mình.
Lola muốn biết: Có bao nhiêu cách xếp bò thỏa mãn quy tắc trên?

Vì con số này rất lớn, hãy giúp Lola tính ra số cách xếp đó.

Input

• Dòng đầu tiên: số nguyên T – số test (1 ≤ T ≤ 111).
• Mỗi test gồm hai số M, N (kích thước thảo nguyên), thỏa mãn M × N ≤ 30.

Output

• Gồm T dòng, mỗi dòng chứa số cách xếp bò của test đó.
-

sample input

1
1 1

Sample output

2

NOTE

Giải thích cho ví dụ trên, vì thảo nguyên có kích thước 1*1, nên chỉ có 1 ô => có 2 cách xếp:
- Cách 1: Để trống ô đó.
- Cách 2: Đặt 1 con bò vào ô đó