You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

Frieren终于起来啦！但是她看到Fern制造的药水十分的不满（她觉得这瓶药水一点技术含量都没有！）。Fern是个要强的孩子，她决定制造更加复杂的药水来证明自己，与Fern一起完成这瓶药水吧！

Description

药水需要按照特定的顺序添加k种材料：1、2、……、k。这k种材料所蕴含的元素各不相同。为了让药水稳定，必须确保在调配过程中，任意连续的k种材料中，每种元素至少各出现一次（即不能缺少任意一种）。给定一个长度为n的材料序列（由k种材料组成），请计算最小需要替换的材料数量，使整个序列满足上述条件。替换时，可以将任意一个材料改为k种材料中的任意一种。

Format

Input

第一行一个整数$T(1 \leq T \leq 100)$，表示测试用例数量。 每个测试用例：

第一行两个整数 $n(3 \leq n \leq 1 \times 10^5)$、$k(3 \leq k \leq 100)$，表示序列长度和元素数量。

第二行一个长度为$n$的数组，由不大于$k$的正整数组成。

Output

对于每个测试用例，输出一行一个整数，表示最小替换次数。

Samples

3
5 3
1 2 1 1 2
6 6
3 1 2 6 4 5
3 3
1 1 1

1
0
2

Note

样例1、替换第三个数为3即可

样例2、任意连续的k个数都包含各个元素至少一次，无需替换

Limitation

Time Limit: 2 second

Memory Limit: 256MiB