The Least Possible Effort

Source: UVa

Version: Phuoc Hung OJ Extended

Problem Statement

In a Knight's tour, a starting square is chosen and the knight is moved so that every square of the board is visited exactly once.

If two starting squares can be transformed into one another by a symmetry of the entire board, checking one represents the other: reflecting or rotating a valid tour produces a corresponding valid tour.

Given an $n$ by $m$ rectangular board, find the minimum number of starting squares that must be examined to represent every equivalence class under the board's symmetries.

Input

One line contains two integers $n$ and $m$, the number of rows and columns.

Output

Print the minimum number of starting positions that must be examined.

Subtasks

• Subtask 1 (20%): $n\ne m$ and both dimensions are even.
• Subtask 2 (30%): $n\ne m$ and at least one dimension is odd.
• Subtask 3 (50%): Full constraints: $6\le n,m\le10000$; $n=m$ is allowed.

Examples

Input

6 9

Output

15

Explanation

Number the rows from $1$ through $6$. Reflection across the horizontal axis pairs them as (1,6), (2,5), and (3,4).

Number the columns from $1$ through $9$. Reflection across the vertical axis gives the five groups (1,9), (2,8), (3,7), (4,6), and {5}.

Because the board is $6\times9$, a $90^\circ$ rotation cannot interchange rows and columns. Each position class is determined by one row group and one column group, giving

classes to represent. Therefore the program prints 15.