소수 분할

수학과가 전산학과에 이산수학 퍼즐을 하나 냈다.

양의 정수 $n$개로 이루어진 수열이 주어진다. 이 수열을 연속한 구간 $k$개로 나눈다. 각 구간에는 정수가 적어도 하나 들어가야 하고, 구간을 순서대로 이으면 원래 수열이 된다.

분할의 점수는 이렇게 매긴다. 각 구간마다 그 구간의 모든 정수를 나누는 가장 큰 소수를 찾는다. 소수는 1보다 큰 정수 중 약수가 1과 자기 자신뿐인 수다. 구간의 모든 정수를 나누는 소수가 없으면 그 구간의 점수는 0이다. 분할의 점수는 구간 점수 중 가장 작은 값이다.

$k$개 구간으로 나누는 분할이 얻는 점수의 최댓값을 구하라.

첫째 줄에 수열의 길이 $n$과 구간의 개수 $k$가 주어진다 ($1 \le n \le 20000$, $1 \le k \le \min(100, n)$).

둘째 줄에 수열을 이루는 정수 $v_1, v_2, \dots, v_n$이 순서대로 주어진다 ($1 \le v_i \le 1000000$).

$k$개 구간으로 나누는 분할이 얻는 최대 점수를 정수 하나로 출력한다.