Description

The Game of Life is a classic zero-player game.

The game is played on an $n \times m$ grid board. Initially, some cells contain life, and the others do not.

When a new day begins, if among the 8 neighboring cells around a cell (cells on the boundary may have fewer than 8 neighbors), there were exactly $2$ or $3$ living cells on the previous day, then the life in this cell can continue to survive. If among the neighboring cells there were exactly $3$ living cells on the previous day and this cell was not alive on the previous day, then new life is born in this cell. In all other cases, any existing life in this cell dies, and no new life is created.

If on some day, there is no life in any cell on the board, then obviously in the following days there will never be life in any cell again. We say that life has gone extinct.

Now, Niuniu wants Feifei to decide whether each cell on the board is alive at the start of the game.

He wants to know how many different initial configurations Feifei can choose so that life on the board will never go extinct.

Input Format

The input contains multiple test cases. The first line contains an integer $T$ indicating the number of test cases. ($T <= 30$)

Then each test case is described as follows:

• One line with $2$ positive integers $n$ and $m$. ($n,m<=5$)

Output Format

For each test case, output $1$ line:

• Output one integer, representing the answer.

2
2 2
3 3

5
150

Hint

From the 2018 Tsinghua University Programming Contest and College Invitational Contest (THUPC 2018). Thanks to Pony.ai for supporting this contest.

Resources such as editorials can be found at https://github.com/wangyurzee7/THUPC2018.

Translated by ChatGPT 5