เสี่ยว $\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$