الصغيرة $\varepsilon$ والصغيرة $\omega$ فتاتان تعشقان الموسيقى. تخليدًا لذكرى تخصهما وحدهما، كتبت الصغيرة $\varepsilon$ لحنًا للصغيرة $\omega$.

سجلت الصغيرة $\varepsilon$ كل نغمة في المقطوعة كعدد صحيح وفقًا لطبقتها الصوتية. اختارت جملة موسيقية $a$ طولها $k$ بحيث تكون $a$ إزاحة دائرية للمتتالية $[1, 2, \dots, k]$، أي أنه يوجد عدد صحيح غير سالب $p$ ($0 \le p < k$) بحيث يكون $a = [p + 1, p + 2, \dots, k, 1, 2, \dots, p]$. بعد ذلك، كررت هذه الجملة الموسيقية مرارًا وتكرارًا وأخذت أول $n$ نغمات لتحصل على النوتة الأصلية $b$.

على سبيل المثال، عندما يكون $k = 4$، يمكن أن تكون $a$ إحدى المتتاليات $[1, 2, 3, 4]$ أو $[2, 3, 4, 1]$ أو $[3, 4, 1, 2]$ أو $[4, 1, 2, 3]$. إذا كانت $a = [2, 3, 4, 1]$ و $n = 10$، فإن $b = [2, 3, 4, 1, 2, 3, 4, 1, 2, 3]$.

قبل إهداء اللحن إلى الصغيرة $\omega$، أرادت الصغيرة $\varepsilon$ أن تضفي لمستها الخاصة على اللحن: يمكنها إجراء أي عدد من التعديلات، وفي كل تعديل يمكنها تغيير النغمة الموجودة في أي موضع في النوتة إلى أي عدد صحيح موجب. بعد عدة تعديلات، تحولت النوتة الأصلية $b$ إلى النوتة التي سمعتها الصغيرة $\omega$ في النهاية، وهي $b'$.

سمعت الصغيرة $\omega$ هذا اللحن $b'$، وعرفت العدد $k$ من تمتمة الصغيرة $\varepsilon$ أثناء نومها. الآن تريد الصغيرة $\omega$ معرفة أقل عدد من النغمات التي عدلتها الصغيرة $\varepsilon$ لتحويل النوتة الأصلية $b$ إلى النوتة $b'$ التي سمعتها في النهاية.

الإدخال

يحتوي السطر الأول على عدد صحيح $T$ ($1 \le T \le 10^4$)، يمثل عدد حالات الاختبار.

تتكون كل حالة اختبار من سطرين:

• يحتوي السطر الأول على عددين صحيحين $n, k$ ($2 \le k \le n \le 2 \times 10^5$)، يمثلان طول النوتة وطول الجملة الموسيقية على التوالي.
• يحتوي السطر الثاني على $n$ أعداد صحيحة $b'_1, b'_2, \dots, b'_n$ ($1 \le b'_i \le 10^9$)، تمثل الطبقات الصوتية للنغمات التي سمعتها الصغيرة $\omega$ في النهاية.

يُضمن أن مجموع $n$ عبر جميع حالات الاختبار في ملف اختبار واحد لا يتجاوز $2 \times 10^5$.

الإخراج

لكل حالة اختبار، اطبع سطرًا واحدًا يحتوي على عدد صحيح غير سالب يمثل أقل عدد من النغمات التي عدلتها الصغيرة $\varepsilon$.

أمثلة

الإدخال 1

8
6 3
2 3 1 2 3 1
5 3
1 2 3 1 3
5 4
4 3 2 1 4
6 3
1 3 1 3 1 3
5 2
1 1 1 1 1
6 4
1 2 3 4 5 6
6 2
172 723 593 904 219 576
5 3
3 1 1000000000 999999999 1

الإخراج 1

0
1
2
4
2
2
6
2

ملاحظة

في حالة الاختبار الأولى، يمكن اختيار $a = [2, 3, 1]$. عندئذٍ تكون النوتة الأصلية هي $b = [2, 3, 1, 2, 3, 1]$ بالضبط، وهي مطابقة تمامًا للنوتة النهائية، لذلك لم تقم الصغيرة $\varepsilon$ بتعديل أي نغمة.

في حالة الاختبار الثانية، يمكن اختيار $a = [1, 2, 3]$، لنحصل على $b = [1, 2, 3, 1, 2]$. يكفي تغيير النغمة الأخيرة إلى $3$ للحصول على النوتة النهائية، وبالتالي فإن الإجابة هي $1$.

في حالة الاختبار الثالثة، يمكن اختيار $a = [4, 1, 2, 3]$، لنحصل على $b = [4, 1, 2, 3, 4]$. يكفي تغيير النغمة ذات الترتيب $2$ إلى $3$ والنغمة ذات الترتيب $4$ إلى $1$ للحصول على النوتة النهائية، وبالتالي فإن الإجابة هي $2$.