20958번 - 아린과 슬롯머신

아린은 강원랜드로 휴가를 떠났다(아린은 감염병 예방을 위한 정부의 방역지침을 준수한다). 강원랜드에서 가장 인기 있는 게임은 슬롯머신이다. 슬롯머신을 구경하던 아린은 놀라 자빠질 수밖에 없었다. 잭팟이 터질 경우 거액의 당첨금을 받을 수 있다는 정보를 입수하였기 때문이다. 아린은 잭팟을 터트려 집도 사고 차도 사고 맛있는 것도 많이 먹기로 결심하였다.

아린은 칸의 개수가 N개인 슬롯머신을 가지고 있다. 슬롯머신의 레버를 당길 때마다 각 칸에는 임의의 양의 정수가 표시된다. 이때 모든 칸에 7이 표시되면 잭팟이 터졌다고 하며, 잭팟이 터지면 거액의 당첨금이 지급된다.

하지만 슬롯머신을 작동시키기 위해서는 돈이 필요하다. 검소하기로 유명한 아린은 슬롯머신 따위에 돈을 낭비하지 않는다. 슬롯머신을 작동시키는 대신, 아린은 슬롯머신의 각 칸에 대하여 다음과 같은 연산을 무한히 수행할 수 있다. 구간 [i, i + M)과 7이 아닌 소수 p를 선택한다. 그리고 구간에 속하는 수 중 p로 나누어떨어지는 모든 수를 p로 나눈다. 즉, S_i, S_i+1, ..., S_i+M-1 중 p로 나누어떨어지는 모든 수를 p로 나눈다. (1 ≤ i ≤ N - M + 1, p ≠ 7)

슬롯머신의 상태가 주어졌을 때, 잭팟을 터트리기 위하여, 즉 모든 수를 7로 바꾸는 데 필요한 최소 연산 횟수를 구하는 프로그램을 작성하시오.

첫 번째 줄에 슬롯머신의 칸의 개수 N과 구간의 길이 M이 주어진다.

두 번째 줄에 슬롯머신의 각 칸에 표시된 N개의 정수 S₁, S₂, ..., S_N이 주어진다.

모든 입력은 공백으로 구분되어 주어진다.

첫 번째 줄에 잭팟을 터트리기 위하여 필요한 최소 연산 횟수를 출력한다. 모든 수를 7로 바꿀 수 없다면 -1을 출력한다.

• 1 ≤ N ≤ 50,000
• 1 ≤ M ≤ N
• 1 ≤ S_i ≤ 10,000,000

입력의 양이 방대하므로 빠른 입력을 사용할 것을 권장한다.