该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

量子共振

题目背景

在 30XX 年，人类发明了“量子谐波传送技术”。作为星际联邦的特级探员，你正在渗透敌方的一座线性防御基地。

题目描述

基地的内部是一条笔直的长廊，地面上铺设了 $n$ 块充能地板，编号依次为 $1$ 到 $n$。每块地板 $i$ 都在以特定的振动频率 $a_i$ 进行量子震荡。

你的目标是从入口（地板 $1$）尽快移动到核心控制室（地板 $n$）。由于量子物理的限制，你只能在两块地板 $i$ 和 $j$ 之间进行一次“相位跳跃”，当且仅当同时满足以下两个物理法则：

1. 谐波纠缠法则：

   起跳点和落点的振动频率必须存在共鸣。数学上定义为：两个频率必须拥有至少一个共同的质因子。

   即：$\gcd(a_i, a_j) > 1$。

2. 隧穿距离限制：

   你的量子推进器能量有限，单次跳跃的直线距离不能超过 $k$。

   即：$|i - j| \le k$。

每次跳跃消耗 1 个单位的时间。请计算出抵达地板 $n$ 所需的最少时间。如果物理上无法抵达，请输出 -1。

输入格式

第一行包含两个整数 $n$ 和 $k$ $(2 \le n \le 2 \times 10^5, 1 \le k \le n)$，分别代表地板的数量和最大跳跃距离。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 10^6)$，表示第 $i$ 块地板的振动频率。

输出格式

输出一个整数，表示从地板 $1$ 跳跃到地板 $n$ 的最少次数。若无法到达，输出 -1。

输入输出样例 #1

输入 #1

6 2
6 10 15 21 14 9

输出 #1

3

输入输出样例 #2

输入 #2

5 1
2 3 5 7 11

输出 #2

-1

输入输出样例 #3

输入 #3

9 3
5 30 21 36 21 25 30 24 4

输出 #3

4

说明/提示

对于样例 1，路径：$1 \to 3 \to 4 \to 6$。

对于样例 3，一种可行路径：

1. $1 \to 2$：$|1-2|=1 \le 3$, $\gcd(5, 30)=5$.

2. $2 \to 4$：$|2-4|=2 \le 3$, $\gcd(30, 36)=6$.

3. $4 \to 7$：$|4-7|=3 \le 3$, $\gcd(36, 30)=6$.

4. $7 \to 9$：$|7-9|=2 \le 3$, $\gcd(30, 4)=2$.

   共 4 步。