LASER_BEAM - Laser Beam

no tags 


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.


hide comments
Sushovan Sen: 2019-04-22 13:17:38

Problem is easier than what the number of solvers suggest.

gerson34: 2016-10-11 22:11:33

Any suggestion, please....I am very time in this problem........

Last edit: 2016-10-11 22:12:57
entangler: 2016-03-22 04:24:45

I'm working on this question since last two days. But getting TLE. Can anyone please give some hint.

raghav12345: 2016-02-03 10:05:29

one of my shortest code
but took 3 hr to understand
nice one :)

[Rampage] Blue.Mary: 2016-01-20 06:29:05

Warning: The sample test cases are well-designed to mislead you, although they are correct.

darryl: 2015-11-17 03:39:09

Fun problem.

(Tjandra Satria Gunawan)(曾毅昆): 2015-11-15 02:13:12

@ghjklfd: your code is wrong, you should find out the case that fail your code yourself, that's the purpose of this problem :)

ghjklfd: 2015-11-14 18:52:54

WA again and again. Any tricky test cases ?

ghjklfd: 2015-11-14 18:52:22

@Tjandra: Which explanation and proof ?

(Tjandra Satria Gunawan)(曾毅昆): 2015-11-14 10:23:46

@Alex Anderson: Thank you very much! Your explanation & proof is very useful :)


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