SP25690 LASER_BEAM - Laser Beam

 _5 × 9 grid without laser beam_  _5 × 9 grid with laser beam_Jolly Kingdom is threatened by the arrival of an evil witch. In order to protect the kingdom, the king wants to install some powerful laser beams to cover some parts of the kingdom. The part that needs to be protected has size of N × M. To complete this installation, he hired you, as the best engineer he can find. Imagine a grid of size N × M, you can choose one node in the grid and shot a laser beam, the laser can be shot only in diagonal direction as shown in the picture above, if the laser reach the edge of the grid, it'll bounce to other diagonal direction, and if the laser reach the corner of the grid, it'll bounce back. The laser will form a loop track. In order to install the best security laser beam for the king, you have to compute the number of different laser track.

First line consists of an integer T (1

For each test case, output an integer – the number of different laser track on that grid.