Đoạn nguyên tố

Cho một dãy số nguyên dương $A=(a_1,a_2,\dots ,a_n)$ ($a_i\le {10}^6$; $1\le i\le n$). Với mỗi phần tử $a_i$ bạn được phép tăng hoặc giảm một lượng tùy ý để được một số nguyên tố. Khi đó chi phí của bạn cần bỏ ra chính là lượng tăng hoặc giảm đó (một phần tử đã là số nguyên tố thì có chi phí $0$; lưu ý $1$ không phải là số nguyên tố, và số nguyên tố nhận được có thể lớn hơn ${10}^6$).

Yêu cầu: Hãy chọn ra một đoạn con gồm $k$ phần tử liên tiếp nhau của dãy $A$ sao cho tổng chi phí biến đổi mọi phần tử trong đoạn con đó thành các số nguyên tố là nhỏ nhất.

Dữ liệu vào

• Dòng 1: Chứa hai số nguyên dương $n,k$ ($1\le k\le n\le {10}^5$).
• Dòng 2: Chứa $n$ số nguyên dương $a_1,a_2,\dots ,a_n$ ($a_i\le {10}^6$, $\forall i=1,2,\dots ,n$).

Dữ liệu ra

In ra một số nguyên duy nhất là tổng chi phí biến đổi nhỏ nhất tìm được.

Ràng buộc

• $1\le k\le n\le {10}^5$.
• $1\le a_i\le {10}^6$ với mọi $i=1,2,\dots ,n$.

Subtasks

Điểm được tính theo từng test.

• Subtask 1 ($20\%$ số test): $a_i$ đều là số nguyên tố, $\forall i=1,2,\dots ,n$.
• Subtask 2 ($40\%$ số test): $n,k\le 5000$; $a_i\le 5000$, $\forall i=1,2,\dots ,n$.
• Subtask 3 ($40\%$ số test): không có ràng buộc bổ sung.

Ví dụ