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 W-by-H 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 W-by-H 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 64-bit signed integer and less than 10¹⁵.

You may try M3TILE, M4TILE, or M5TILE first.

See also: Another problem added by Tjandra Satria Gunawan