310536: CF1848B. Vika and the Bridge

B. Vika and the Bridgetime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

In the summer, Vika likes to visit her country house. There is everything for relaxation: comfortable swings, bicycles, and a river.

There is a wooden bridge over the river, consisting of $n$ planks. It is quite old and unattractive, so Vika decided to paint it. And in the shed, they just found cans of paint of $k$ colors.

After painting each plank in one of $k$ colors, Vika was about to go swinging to take a break from work. However, she realized that the house was on the other side of the river, and the paint had not yet completely dried, so she could not walk on the bridge yet.

In order not to spoil the appearance of the bridge, Vika decided that she would still walk on it, but only stepping on planks of the same color. Otherwise, a small layer of paint on her sole will spoil the plank of another color. Vika also has a little paint left, but it will only be enough to repaint one plank of the bridge.

Now Vika is standing on the ground in front of the first plank. To walk across the bridge, she will choose some planks of the same color (after repainting), which have numbers $1 \le i_1 < i_2 < \ldots < i_m \le n$ (planks are numbered from $1$ from left to right). Then Vika will have to cross $i_1 - 1, i_2 - i_1 - 1, i_3 - i_2 - 1, \ldots, i_m - i_{m-1} - 1, n - i_m$ planks as a result of each of $m + 1$ steps.

Since Vika is afraid of falling, she does not want to take too long steps. Help her and tell her the minimum possible maximum number of planks she will have to cross in one step, if she can repaint one (or zero) plank a different color while crossing the bridge.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5$) — the number of planks in the bridge and the number of different colors of paint.

The second line of each test case contains $n$ integers $c_1, c_2, c_3, \dots, c_n$ ($1 \le c_i \le k$) — the colors in which Vika painted the planks of the bridge.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output a single integer — the minimum possible maximum number of planks that Vika will have to step over in one step.

ExampleInput

5
5 2
1 1 2 1 1
7 3
1 2 3 3 3 2 1
6 6
1 2 3 4 5 6
8 4
1 2 3 4 2 3 1 4
3 1
1 1 1

Output

0
1
2
2
0

Note

In the first test case, Vika can repaint the plank in the middle in color $1$ and walk across the bridge without stepping over any planks.

In the second test case, Vika can repaint the plank in the middle in color $2$ and walk across the bridge, stepping over only one plank each time.

In the third test case, Vika can repaint the penultimate plank in color $2$ and walk across the bridge, stepping only on planks with numbers $2$ and $5$. Then Vika will have to step over $1$, $2$ and $1$ plank each time she steps, so the answer is $2$.

In the fourth test case, Vika can simply walk across the bridge without repainting it, stepping over two planks each time, walking on planks of color $3$.

In the fifth test case, Vika can simply walk across the bridge without repainting it, without stepping over any planks.

题目大意：
Vika喜欢在夏天去她的乡间别墅，那里有一座由n块木板组成的木桥。Vika决定给桥刷上k种颜色的油漆。为了避免弄坏未干的油漆，Vika决定只踩在相同颜色的木板上过桥。Vika还可以重新刷一块木板，以便选择一种颜色踩在上面过桥。求Vika过桥时，每次踩过的木板的最大数量最少是多少。

输入数据格式：
第一行包含一个整数t，表示测试用例的数量。
每个测试用例包含两行：
第一行包含两个整数n和k，分别表示木板的数量和油漆的颜色数量。
第二行包含n个整数c1, c2, ..., cn，表示每块木板的颜色。

输出数据格式：
对于每个测试用例，输出一个整数，表示Vika过桥时每次踩过的木板的最大数量最少是多少。

示例：
输入：
5
5 2
1 1 2 1 1
7 3
1 2 3 3 3 2 1
6 6
1 2 3 4 5 6
8 4
1 2 3 4 2 3 1 4
3 1
1 1 1

输出：
0
1
2
2
0

注意：
在第一个测试用例中，Vika可以重新刷中间的木板为颜色1，然后不用踩任何木板过桥。
在第二个测试用例中，Vika可以重新刷中间的木板为颜色2，然后每次只踩一块木板过桥。
在第三个测试用例中，Vika可以重新刷倒数第二块木板为颜色2，然后只踩编号为2和5的木板过桥，每次踩过的木板数量为1, 2, 1，所以答案是2。
在第四个测试用例中，Vika可以直接踩颜色为3的木板过桥，每次踩两块木板。
在第五个测试用例中，Vika可以直接踩相同颜色的木板过桥，不用踩任何木板。题目大意： Vika喜欢在夏天去她的乡间别墅，那里有一座由n块木板组成的木桥。Vika决定给桥刷上k种颜色的油漆。为了避免弄坏未干的油漆，Vika决定只踩在相同颜色的木板上过桥。Vika还可以重新刷一块木板，以便选择一种颜色踩在上面过桥。求Vika过桥时，每次踩过的木板的最大数量最少是多少。 输入数据格式： 第一行包含一个整数t，表示测试用例的数量。 每个测试用例包含两行： 第一行包含两个整数n和k，分别表示木板的数量和油漆的颜色数量。 第二行包含n个整数c1, c2, ..., cn，表示每块木板的颜色。 输出数据格式： 对于每个测试用例，输出一个整数，表示Vika过桥时每次踩过的木板的最大数量最少是多少。 示例： 输入： 5 5 2 1 1 2 1 1 7 3 1 2 3 3 3 2 1 6 6 1 2 3 4 5 6 8 4 1 2 3 4 2 3 1 4 3 1 1 1 1 输出： 0 1 2 2 0 注意： 在第一个测试用例中，Vika可以重新刷中间的木板为颜色1，然后不用踩任何木板过桥。 在第二个测试用例中，Vika可以重新刷中间的木板为颜色2，然后每次只踩一块木板过桥。 在第三个测试用例中，Vika可以重新刷倒数第二块木板为颜色2，然后只踩编号为2和5的木板过桥，每次踩过的木板数量为1, 2, 1，所以答案是2。 在第四个测试用例中，Vika可以直接踩颜色为3的木板过桥，每次踩两块木板。 在第五个测试用例中，Vika可以直接踩相同颜色的木板过桥，不用踩任何木板。