题目描述

现在有 $n$ 位学生，编号为 $1, 2, 3, \cdots, n$，初始 好感度 依次为 $a_1, a_2, a_3, \cdots, a_n$。老师在每一天可以执行以下操作恰好一次：

• 选取整数 $l, r$ 满足 $1 \leq l \leq r \leq n$，令所有编号属于 $[l, r]$ 的学生的好感度增加 $1$。具体地，对于所有整数 $i$ ($l \leq i \leq r$)，令 $a_i := a_i + 1$。

现在，老师希望通过尽量少的天数使得学生们的好感度数列 $a_1, a_2, a_3, \cdots, a_n$ 中至多出现 $m$ 种不同的数。他找来了你帮忙求出天数的最小值。

输入格式

本题包含多组测试数据。

首先在第一行输入一个正整数 $T$ ($1 \leq T \leq 10$) 表示测试数据组数。

对于每一组测试数据：

第一行包含两个整数 $n, m$ ($1 \leq n \leq 400, 1 \leq m \leq 2$)，表示学生的数量和求解答案所需的参数。

第二行包含 $n$ 个正整数 $a_1, a_2, a_3, \cdots, a_n$ ($0 \leq a_i \leq 100$)，表示每个学生的初始好感度。

输出格式

对于每一组测试数据，输出包含一行一个非负整数表示天数的最小值。

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

2
12
3
1