This problem is a programming version of Problem 228 from projecteuler.net
Let be the regular -sided polygon – or shape – whose vertices () have coordinates:
Each is to be interpreted as a filled shape consisting of all points on the perimeter and in the interior.
The Minkowski sum, , of two shapes and is the result of adding every point in to every point in , where point addition is performed coordinate-wise: .
For example, the sum of and is the six-sided shape shown in pink below:
Given two integers and , how many sides does the Minkowski sum have?
Input Format
The first line of each test file contains a single integer which is the number of queries.
Each of the next lines contains two space-separated integers, and .
Constraints
- .
- .
- The sum of over all queries .
Output Format
Print the answer to each query in a new line.
Sample Input 0
1
3 4
Sample Output 0
6
Explanation 0
The figure in the problem description shows .
We can see that the number of sides of that shape is .
Sample Input 1
1
4 5
Sample Output 1
8
Explanation 1
Sample Input 2
1
3 5
Sample Output 2
10
Explanation 2
