Little O‘s house need to put ground tile. The house is M x N (1 <= M <= 9, 1 <= N <= 9). His girlfriend brought some strange tile: 1) rectangles (2x1) 2) corners (squares 2x2 without one 1x1 square) You have to determine X - the number of ways to cover the ground.Remarks. The number of pieces is large enough. It is not allowed to leave empty places, or to cover any part of a surface twice, or to saw pieces.

There are multiple test cases. The first line of input is an integer T (0 < T <= 100) Then T test cases follow. The i-th line of the next T lines contains two dates, natural number M and natural number N.

There should be T lines. Each line should contain the number X, or 0 if there are no solutions.

tyh