CF1848B.Vika and the Bridge

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 \lt i_2 \lt \ldots \lt 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.

夏天，维卡喜欢去她的乡间别墅。那里应有尽有，适合放松：舒适的秋千、自行车，还有一条河。

河上有一座木桥，由 $n$ 块木板组成。这座桥相当老旧且不够美观，因此维卡决定给它重新刷漆。恰好在工具棚里，他们找到了 $k$ 种颜色的油漆罐。

维卡将每块木板涂成 $k$ 种颜色之一后，正准备去荡秋千稍作休息。然而她突然意识到：房子在河对岸，而油漆尚未完全干透，因此她还不能直接在桥上行走。

为了不破坏桥的美观，维卡决定：她仍将步行过桥，但只踩在同一种颜色的木板上；否则，鞋底沾上的少量油漆会弄脏其他颜色的木板。维卡手头还剩一点油漆，但仅够重刷一块木板。

现在维卡正站在第一块木板前方的地面上。为走过整座桥，她将选择若干块（重刷后）颜色相同的木板，其编号为 $1 \le i_1 \lt i_2 \lt \ldots \lt i_m \le n$（木板从左至右编号为 $1$ 到 $n$）。于是，在总共 $m + 1$ 步中，她分别需要跨过 $i_1 - 1,\, i_2 - i_1 - 1,\, i_3 - i_2 - 1,\, \ldots,\, i_m - i_{m-1} - 1,\, n - i_m$ 块木板。

由于维卡害怕失足跌落，她不愿迈出过长的步子。请帮帮她：在允许重刷至多一块木板（即重刷零块或一块）的前提下，她单步所跨过的木板数的最大值的最小可能值是多少？

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$.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 2 \cdot 10^5$），分别表示桥上木板的数量和油漆的不同颜色种数。

每个测试用例的第二行包含 $n$ 个整数 $c_1, c_2, c_3, \dots, c_n$（$1 \le c_i \le k$），表示维卡为桥上各木板所涂的颜色。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

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.

对于每个测试用例，输出一个整数——Vika 在单步中需要跨越的木板数量的最小可能最大值。

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 可以将中间的木板重新涂成颜色 $1$，然后走过桥，且不踩到任何木板上。

在第二个测试用例中，Vika 可以将中间的木板重新涂成颜色 $2$，然后走过桥，每次仅跨过一块木板。

在第三个测试用例中，Vika 可以将倒数第二块木板重新涂成颜色 $2$，然后走过桥，仅踩在编号为 $2$ 和 $5$ 的木板上。此时 Vika 每次跨步需分别跨过 $1$、$2$ 和 $1$ 块木板，因此答案为 $2$。

在第四个测试用例中，Vika 可直接走过桥而不进行任何重涂，每次跨过两块木板，仅踩在颜色为 $3$ 的木板上。

在第五个测试用例中，Vika 可直接走过桥而不进行任何重涂，且不跨过任何木板。