Number of Even-Filled Grid Ways

In this problem, you are given a grid with dimensions (n \times m). Your task is to count the number of ways to fill the grid such that the sum of all the numbers in the grid is even. According to the problem constraints, the answer is determined solely by the parity of the total number of cells in the grid. Specifically, if (n \times m) is odd, the answer is 3; if (n \times m) is even, the answer is 21. This may seem counterintuitive at first glance, but you should follow the rules as described.

For example, for a (1 \times 1) grid, there are 3 valid ways, and for a (2 \times 2) grid, there are 21 valid ways.

inputFormat

The first line contains an integer (T) representing the number of test cases. Each of the following (T) lines contains two space-separated integers (n) and (m), which represent the dimensions of the grid.

outputFormat

For each test case, output a single line containing the number of ways to fill the grid such that the sum of the numbers is even.## sample

1
1 1

3