Sequence

Interview

Time limit1sMemory limit128 MB

Summary

Given up to five strictly increasing numbers, find the smallest base at most 10 in which their values, read as base-b numerals, form an arithmetic sequence.

Level: Easy3 of 10
Topics: Math, Brute force
Solved: No attempts yet

Problem

We call a sequence of numbers an arithmetic sequence in base $b$ if, when each number is read as a base- $b$ numeral, consecutive terms differ by a constant.

For example, $1, 1010, 2012, 10021$ is an arithmetic sequence in base $3$ , and $11, 33, 55$ is an arithmetic sequence not only in base $10$ but also in base $6$ .

Given a sequence of numbers, find the smallest base (at most $10$ ) in which the numbers form an arithmetic sequence.

If the largest digit appearing in any number is $d$ , then the base must be at least $d+1$ for every digit to be valid, and it is always at least $2$ .

Input

The input consists of several test cases.

The first line of each test case contains an integer $n$ ( $2 \le n \le 5$ ), the count of numbers in the sequence. The next line contains the $n$ numbers in strictly increasing order, separated by single spaces.

A line containing $n = 0$ terminates the input. Every number is positive, uses only the digits $0$ through $9$ , and has at most $5$ digits.

Output

For each test case, print a single line.

If such a base exists, print

Minimum base = x.

where $x$ is the smallest base $\le 10$ that yields an arithmetic sequence. Otherwise, print

No base <= 10 can be found.

Examples1

Example 1

Input

4
1 1010 2012 10021
3
11 33 55
4
11 33 55 77
5
10 160 340 520 1000
5
10 160 340 520 10000
0

Expected output

Minimum base = 3.
Minimum base = 6.
Minimum base = 8.
Minimum base = 7.
No base <= 10 can be found.