We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

- All Contests
- ProjectEuler+
- Project Euler #228: Minkowski Sums

# Project Euler #228: Minkowski Sums

# Project Euler #228: Minkowski Sums

Contest ends in

_{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**