数学系向你们大学的计算机科学系发起挑战，要求解决一道离散数学中的难题。为了维护计算机科学系的荣誉，你必须解决这个谜题！

在这个谜题中，你将得到一个包含 $n$ 个正整数的序列。该序列必须被划分为 $k$ 个连续的区域，且每个区域至少包含一个整数。划分完成后，将以一种特殊的方式进行评分。在每个区域中，你必须找到能够整除该区域内所有数字的最大质数。数学系提醒你，质数是指大于 1 且仅能被 1 和它本身整除的整数。如果你无法找到这样的质数，那么该区域的得分为 0。你对该划分的总得分为所有区域得分中的最小值。

你的任务是找到可能的最大总得分。如果数学系的得分比你高，他们就会获胜，所以请务必每次都找到最大值！

输入格式

每个输入包含一个测试用例。注意，你的程序可能会在不同的输入上运行多次。每个输入的第一行包含两个空格分隔的整数 $n$ ($1 \le n \le 20\,000$) 和 $k$ ($1 \le k \le \min(100, n)$)，其中 $n$ 是原始序列中正整数的个数，$k$ 是划分的区域数。下一行包含 $n$ 个空格分隔的整数 $v$ ($1 \le v \le 1\,000\,000$)，即需要按顺序进行划分的序列。

输出格式

输出一个整数，表示将 $n$ 个正整数的序列划分为 $k$ 个区域时可能获得的最大得分。

样例

样例输入 1

5 3
10 5 4 8 3

样例输出 1

2

样例输入 2

5 3
10 11 12 13 14

样例输出 2

0