MNTILE  Tiling a WxH Grid With Dominoes
Write a program that takes as input the width, W and height H of the grid and outputs the number of different ways to tile a WbyH grid with (2x1) dominoes.
Score is the length of your source.
Input
The first line is an integer T(1 ≤ T ≤ 276), denoting the number of test cases. Then, T test cases follow.
For each test case, there are two integers W and H(0 ≤ W+H ≤ 22) written in one line, separated by space.
Output
For each test case, output the number of different ways to tile a WbyH grid with (2x1) dominoes.
Example
Input: 6
1 2
2 3
3 4
4 5
5 6
6 7 Output:
1
3
11
95
1183
31529
Information
All outputs will fit on 64bit signed integer and less than 10^{15}.
You may try M3TILE, M4TILE, or M5TILE first.
hide comments
Aditya Pande:
20131215 13:56:31
Thnx finally got AC and i learnt a lot


Aditya Pande:
20131215 13:56:31
how to have the long long as well as the fractional computation


15972125841321:
20131215 13:56:31
@Tjandra can u plz tell why m i getting w.a... my sub id 7266788 thnks


Francky:
20131215 13:56:31
Edit : silly mistake !


Mitch Schwartz:
20131215 13:56:31
Are you sure test data is correct? I've examined my output for all possible inputs.

Added by:  Tjandra Satria Gunawan 
Date:  20120702 
Time limit:  1s 
Source limit:  300B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM32GCC ASM64 MAWK BC CCLANG NCSHARP CPP14 CPP14CLANG COBOL COFFEE DCLANG DDMD DART ELIXIR FANTOM FORTH GOSU GRV JSMONKEY JULIA KTLN NIM NODEJS OBJC OBJCCLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET 
Resource:  Generalization of M3TILE, M4TILE/GNY07H, and M5TILE problems. 