Trong một xưởng làm bánh, ông chủ Godsent giao cho Nghialaptrinh một dãy n nguyên liệu, được đánh số từ 1 đến n.
Mỗi nguyên liệu a[i] thuộc về một loại bánh nhất định.

Ông chủ có k thùng chứa, được đánh số từ 1 đến k.

Ông chủ Godsent muốn Nghialaptrinh kiểm tra các phân đoạn nguyên liệu trên dây chuyền để làm ra những "gói bánh tuyệt vời".

Những gói bánh được tạo ra từ một phân đoạn nguyên liệu [l, r] sẽ được gọi là tuyệt vời nếu:

• Tất cả nguyên liệu trong đoạn con [l, r] được đưa vào thùng số 1.
• Tất cả các nguyên liệu còn lại (nằm ngoài đoạn con) có thể được phân chia tùy ý vào bất kỳ trong k thùng (bao gồm cả thùng số 1).
• Sau khi phân chia xong, cả k thùng đều chứa chính xác cùng một số lượng nguyên liệu của mỗi loại bánh.

Do quá kém trong việc lập trình, nên bạn hãy giúp Nghialaptrinh: Đếm số lượng đoạn con tuyệt vời nhé.

Input

• Dòng đầu tiên chứa số nguyên t (1 ≤ t ≤ 1000) - số lượng test case
• Dòng đầu tiên của mỗi test case chứa hai số nguyên n và k (1 ≤ n ≤ 2 * 10^5, 1 ≤ k ≤ n) — số lượng nguyên liệu và số lượng thùng.
• Dòng thứ hai chứa n số nguyên a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ n) — Các loại nguyên liệu.

• Tổng tất cả các test case không vượt quá 2*10^5

  Output

• In ra một số nguyên duy nhất — số lượng đoạn con tuyệt vời.

Example

Input

4
3 2
1 1 1
4 2
1 2 1 2
8 2
3 3 3 3 2 2 2 2
6 3
1 1 1 1 1 1

Output

0
7
18
11

Giải thích test case:

test case 2: n = 4, a = [1, 2, 1, 2], k = 2

Tổng cộng có 2 nguyên liệu loại 1 và 2 nguyên liệu loại 2.

Muốn chia đều cho 2 thùng thì mỗi thùng phải có 1 nguyên liệu loại 1 và 1 nguyên liệu loại 2.

a[1->1] -> Thùng 1 chứa [1] -> còn lại [2,1,2]. Ta phân chia cho [2] vào thùng 1 -> [1,2] và đưa [1,2] còn lại vào thùng 2 -> [1,2]

-> Thùng 1 [1,2] = Thùng 2 [1,2] -> 1

a[2->2] -> Thùng 1 [2,1] = Thùng 2 [1,2] -> 2

a[3->3] -> Thùng 1 [1,2] = Thùng 2 [1,2] -> 3

a[4->4] -> Thùng 1 [2,1] = Thùng 2 [1,2] -> 4

a[1->2] -> Thùng 1 [1,2] = Thùng 2 [1,2] -> 5

a[2->3] -> Thùng 1 [2,1] = Thùng 2 [1,2] -> 6

a[3->4] -> Thùng 1 [1,2] = Thùng 2 [1,2] -> 7 -> answer

a[1->3] -> Thùng 1 [1,2,1] ≠ Thùng 2 [2]