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.

Input

First line consists of an integer T (1 ≤ T ≤ 104) – the number of test cases. Each of next T lines consists an 2 integers N and M (2 ≤ N, M ≤ 109) – the size of the grid.

Output

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

Example

Input:
9
2 2
2 3
3 3
3 5
4 4
5 5
5 9
5 123456789
123456789 5 Output:
2
2
3
3
4
5
5
5
5

Explanation

There are 5 different laser tracks on 5 × 9 grid, shown in the picture above as black line, blue line, pink line, orange line, and green line.


Added by:Tjandra Satria Gunawan
Date:2015-11-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Own Problem, used in Jolly Challenge #10

hide comments
2015-11-14 08:31:27 Alex Anderson
A little on the easier side, requires some analysis, I hope more will solve. Thank you for the problem.

Problem setter: I include another submission where I explain how I got to concise code.

Last edit: 2015-11-14 08:35:48
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.