Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2678
Bishops on a Toral Board

Time Limit: 5 Seconds      Memory Limit: 32768 KB

A bishop is a chess piece that can move in any diagonal direction to any number of cells.

Imagine that we take a board of a size m × n and connect its top and bottom edges, and its left and right edges, so that it would have a form of a torus. For example, on a 7 × 10 board the neighbours of a cell (4,1) would be (3,10) , (3,1) , (3,2) , (4,10) , (4,2) , (5,10) , (5,1) , (5,2) ; the neighbours of a cell (1,10) --- (7,9) , (7, 10) , (7,1) , (1,9) , (1,1) , (2,9) , (2,10) , (2,1) .

On a toral board chess pieces are no longer limited with the edges, and, for example, on a 7 × 10 board a bishop from any cell can move to any other cell of the board in one turn, say, from cell (2,1) to cell (7,9) by a path (2,1) --> (1,10) --> (7,9) .

Let us say that a set of bishops covers the board if one can move some bishop to any free cell in one turn. In other words, each cell is either occupied or threatened by some bishop.

Your task is to find out what is the minimal number of bishops one needs to cover the m × n toral board.

Input

There are several test cases in the input. Each case contains m and n separated by a space (1 <= n, m <= 10100 ). There is an empty line between cases.

Output

Output the minimal number of bishops needed to cover the m × n toral board. There should be an empty line between cases.

Example

InputOutput
2 22
7 101

Source: Andrew Stankevich's Contest #8
Submit    Status