Primal Partitions

The math department challenged the computer science department to a puzzle in discrete mathematics.

You are given a sequence of $n$ positive integers. Split the sequence into $k$ consecutive regions. Every region holds at least one integer, and joining the regions in order gives back the original sequence.

A partition is scored like this. For each region, find the largest prime that divides every integer in that region. A prime is an integer greater than 1 whose only divisors are 1 and itself. If no prime divides every integer of the region, that region scores 0. The score of the partition is the smallest region score.

Find the largest score a partition into $k$ regions reaches.

The first line contains the length of the sequence $n$ and the number of regions $k$ ($1 \le n \le 20000$, $1 \le k \le \min(100, n)$).

The second line contains the $n$ integers $v_1, v_2, \dots, v_n$ of the sequence, in order ($1 \le v_i \le 1000000$).

Print one integer, the maximum score over all partitions of the sequence into $k$ regions.