{"code":"22c2quymao2023","name":"Quý Mão 2023","description":"Vì quá mệt khi phải tìm ý tưởng để viết cốt truyện cho đề ôn Tin học trẻ lần này, Quý quyết định chọn 1 bài tập ngẫu nhiên để làm giải trí. Bài tập mà Quý chọn có đề bài như sau:\r\n\r\nCho $1$ dãy $A$ gồm $n$ số nguyên dương và $1$ số $e$. Hãy đếm số cặp $(i,k)$ thỏa mãn các điều kiện sau:\r\n + $1 \\le i, k$\r\n + $i + e \\times k \\le n$\r\n + Tích $a_i \\times a_{i + e} \\times a_{i + 2e} \\times ... \\times a_{i + ke}$ là 1 số nguyên tố\r\n\r\nNhắc lại, số nguyên tố là số lớn hơn $1$ và chỉ có $2$ ước dương là $1$ và chính nó.\r\n\r\nTuy nhiên, Quý đã không còn đủ sức để làm được bài này nên muốn nhờ các bạn hãy thay Quý giải bài tập trên.\r\n\r\n

Input

\r\n - Dòng đầu tiên gồm số nguyên $t$ ($t \\le 10$) là số lượng test cases của bài toán.\r\n\r\nMỗi test có cấu trúc như sau:\r\n - Dòng đầu tiên bao gồm $2$ số nguyên dương $n$ và $e$ ($1 \\le e \\le n \\le 10^5$) là kích thước của mảng $A$ và số $e$ đề bài cho.\r\n - Dòng thứ $2$ bao gồm $n$ số nguyên dương $a_1, a_2, a_3, ..., a_n$ $(a_i \\le 10^6)$\r\n\r\n

Output

\r\n - Với mỗi test, in ra $1$ số nguyên là số lượng cặp ($i$, $k$) thỏa mãn điều kiện đề bài trên một dòng.\r\n - In ra tổng cộng $t$ dòng cho $t$ test.\r\n\r\n

Scoring

\r\n - Subtask $1$ ($30\\%$ số điểm): $n, e \\le 200, a_i \\le 10^3$\r\n - Subtask $2$ ($30\\%$ số điểm): $e = 1, n \\le 10^5, a_i \\le 10^3$\r\n - Subtask $3$ ($40\\%$ số điểm): Không có ràng buộc gì thêm\r\n\r\n!!! question \"Sample\"\r\n ???+ \"Input\"\r\n ```sample\r\n 6\r\n 7 3\r\n 10 2 1 3 1 19 3\r\n 3 2\r\n 1 13 1\r\n 9 3\r\n 2 4 2 1 1 1 1 4 2\r\n 3 1\r\n 1 1 1\r\n 4 1\r\n 1 2 1 1\r\n 2 2\r\n 1 2\r\n ```\r\n ???+ success \"Output\"\r\n ```sample\r\n 2\r\n 0\r\n 4\r\n 0\r\n 5\r\n 0\r\n ```","points":1500.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}