Document OI: channel.in/out

Title Description

The archaeological team discovered an energy matrix at the Maya ruins. The explorer sets off from the altar in the upper left corner and can only move to the right or down with each step, collecting energy stones along the way (the numbers in each grid represent energy values). The hidden mechanism can only be activated when the greatest common divisor of all energy values on the path is maximized.

Input format

The first line consists of two integers n, m (2 ≤ n, m ≤ 100) Next, n rows with m positive integers per row (values ≤ 1e6)

Output format

The maximum value of the path's greatest common divisor

Example

3 3 
12 6 3
4 8 2
6 3 9

3