John is a farmer who grows vegetables on his farm. Being a very organized sort of
fellow, he wants to subdivide his field into small square plots arranged
in a rectangular grid, being W plots wide by L plots long, with clear straight lanes
running between the plots. He plans on subdividing the plots by the following method:
John will take a piece of colored rope and stake one end into the ground, either at the edge of his farm or at one of the lane intersections. He then walks down an open lane trailing the rope along his path until he reaches an intersection, at which point he does one of the following actions:
- If there is already some rope present in that intersection, then he must stake down the free end of his current rope onto that spot.
- If there isn't any rope yet in that intersection, then he can continue walking along a path in any direction he chooses (except the way he just came from).
- If instead of an intersection he has reached the edge of his farm, then he again must stake down the free end of his current rope onto that spot.
The picture above shows John's first attempt at this method, using a different color for each piece of rope. However after placing only a few pieces of rope according to the rules, he realizes he is wasting quite a bit of time cutting each distinct piece of rope and wonders if he could be using a better strategy which involves less cutting.
While following the rules described above, what is the minimum quantity of distinct pieces of rope required to fully subdivide every plot on the farm?
Problem Statement
Input Data
First line will be Q, the quantity of testcases.
Q lines will then follow each containing two space-separated integers W L, describing a grid
W plots wide by L plots long.
Answer
Should consist of Q space-separated values, being the minimum distinct
pieces of rope required to fully subdivide the field.
Return all answers modulo 1000000007.
Example
input data:
2
1 2
6 4
answer:
1 23