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:

Cho \(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:

• \(1 \le i, k\)
• \(i + e \times k \le n\)
• Tích \(a_i \times a_{i + e} \times a_{i + 2e} \times ... \times a_{i + ke}\) là 1 số nguyên tố

Nhắ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ó.

Tuy 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.

Input

• 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.

Mỗi test có cấu trúc như sau:

• 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.
• 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)\)

Output

• 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.
• In ra tổng cộng \(t\) dòng cho \(t\) test.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n, e \le 200, a_i \le 10^3\)
• Subtask \(2\) (\(30\%\) số điểm): \(e = 1, n \le 10^5, a_i \le 10^3\)
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm

6
7 3
10 2 1 3 1 19 3
3 2
1 13 1
9 3
2 4 2 1 1 1 1 4 2
3 1
1 1 1
4 1
1 2 1 1
2 2
1 2

2
0
4
0
5
0