הקטנה $\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$.