A robot travels over a luminous grid. Initially the grid is off and every time the robot walks over a cell, this cell turns on a light that keeps lighted while the robot keeps moving. The robot can only make to actions: • Take a step forward • Turn 90 degrees clockwise and advance one step forward. The robot always starts from the lower left corner facing the top of the grid. It can do any sequence of movements a and b (it can make many consecutive a movements, or many consecutive b movements, or alternate them in any way) as long as it does not leaves the grid and don’t pass over a previously lighted cell (ie, it can only pass once over every cell). Whenever it’s possible, the robot will keep moving, stopping only when he reaches a cell where he can’t make more movements, ending the route. How many different routes can the robot make over the grid? Example for a grid of 2 rows and 3 columns, where 3 different routes can be done Input The first line of the input contains an integer T, the number of test cases. Each case contains two integers R and C, the number of rows and columns of the grid (2 ≤ R ≤ 25, 1 ≤ C ≤ 25). Output For each case print a line with the number of different routes that the robot can make. Sample Input 4 21 22 23 33 Sample Output 1 2 3 6