Ngày xửa ngày xưa, trong vương quốc u ám nơi Halloween kéo dài quanh năm, có một Nhà Vua Bí Ngô. Ngài sống trong một lâu đài phủ đầy mạng nhện và có một khu vườn ma quái rộng lớn. Trong vườn ấy có $q$ hàng cây bí ngô, mỗi hàng có $n$ cây, cây thứ $i$ cao $a_i$ đơn vị.

Nhà Vua Bí Ngô vốn ám ảnh với sự đối xứng hoàn hảo, nên ông ra lệnh:

Trong mỗi hàng thứ $t$, độ cao của các cây phải tuần hoàn theo một số $k$, nghĩa là cây thứ $i$ phải có độ cao bằng cây thứ $i + k$. Những cây ở cuối hàng (từ cây $n - k + 1$ đến cây $n$) có thể bỏ qua, vì chúng nằm trong vùng bóng tối, nơi không đáng quan tâm.

Một thợ làm vườn tên Drucala, người chuyên tạo hình bí ngô cho các lễ hội, được triệu vào lâu đài. Drucala vừa lo sợ vừa háo hức, quyết tâm tỉa bí sao cho vừa lòng Nhà Vua. Tuy nhiên, hắn vẫn còn đêm Halloween của bản thân, nên hắn muốn tỉa ít nhất có thể để kịp về trước khi đêm trăng máu lên cao.

Hãy giúp Drucala tính xem phải tỉa bao nhiêu cây trong mỗi hàng để khu vườn trở nên "đẹp ma quái" đúng theo ý vua!

Yêu cầu: Với mỗi hàng cây thứ $t$ ($1 \le t \le q$), hãy in ra số lượng cây phải tỉa lại.

Dữ liệu vào

Nhập từ bàn phím:

• Dòng đầu chứa số nguyên $q$ ($1 \le q \le 500$)

$q$ cặp dòng tiếp theo có dạng:

• Dòng đầu tiên chứa 2 số nguyên $n$ và $k$ ($1 \le k \le n \le 10^{4}$)
• Dòng thứ hai chứa các số nguyên $a_i$ (~1 \le a_i \le 10^9~)

Dữ liệu ra

Xuất ra màn hình:

• $q$ dòng yêu cầu của đề bài

Ràng buộc

• Subtask $1$ ($20\%$): $n, q \le 20, a_i \le 100$
• Subtask $2$ ($10\%$): $k = 1, a_i \le 10^{6}$
• Subtask $3$ ($30\%$): $a_i \le 10^{6}$
• Subtask $4$ ($40\%$): Không có ràng buộc gì thêm

Ví dụ

Input

2
6 3
2 3 5 2 3 4
5 2
10 10 20 20 10

Output

1
2

Giải thích

• Ở hàng cây đầu tiên, ta chọn 1 cây là cây thứ $3$ tỉa thành độ cao $4$.
• Ở hàng cây thứ hai, ta chọn 2 cây là cây thứ $3$ và $4$ tỉa thành độ cao $10$.