Arin and the Slot Machine

Arin went on vacation to Kangwon Land (Arin follows the government's disease prevention guidelines). The most popular game at Kangwon Land is the slot machine. While watching the slot machine, Arin could not help but be astonished, because she learned that a jackpot pays out a huge prize. Arin resolved to hit the jackpot, buy a house, buy a car, and eat lots of good food.

Arin has a slot machine with N cells. Each time the lever is pulled, each cell displays an arbitrary positive integer. If all cells display 7, the jackpot has been hit, and a huge prize is paid out.

However, operating the slot machine requires money. Arin, famous for being frugal, does not waste money on something like a slot machine. Instead of operating the slot machine, Arin can perform the following operation infinitely many times on the cells of the slot machine. Choose an interval [i, i + M) and a prime p other than 7. Then divide every number in the interval that is divisible by p by p. That is, among Si, Si+1, ..., Si+M-1, divide every number divisible by p by p. (1 ≤ i ≤ N - M + 1, p ≠ 7)

Given the state of the slot machine, write a program that finds the minimum number of operations needed to hit the jackpot, that is, to turn every number into 7.

The first line gives the number of cells N of the slot machine and the interval length M.

The second line gives the N integers S1, S2, ..., SN displayed in the cells of the slot machine.

All input is separated by spaces.

On the first line, print the minimum number of operations needed to hit the jackpot. If it is impossible to turn every number into 7, print -1.

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

The input is large, so using fast input is recommended.