### 问题描述 在音乐的世界中，小然是一位备受瞩目的新星。他的作品总是充满了新奇和独特，给人带来无尽的惊喜。他的每一首歌，都像一条由音符串成的旅程，每一个音符都传达着他的情感和思考。 最近，小然正在创作一首新歌。他想让这首歌的旋律既独特又和谐，通过一连串的音符，表达他的情感。他认为，一首好的歌曲应当满足以下两个条件： 1. 没有两个相邻的音符是相同的（即音符 $A_i \neq A_{i+1}$）； 2. 最多只有一个音符是"山峰"（比其相邻的音符都高），最多只有一个音符是"谷底"（比其相邻的音符都低）。 小然有两种方法来达到他的目标： 1. 将任意两个音符进行交换，这种操作不需要任何成本； 2. 将任意一个音符替换为一个全新的音符，这种操作的成本为 $K$。 小然可以进行任意多次上述两种操作，最后还可以自由地调整音符的顺序。请你帮助小然计算出，要使得他的歌曲满足上述条件，需要付出的最小代价是多少？ ### 输入格式 第一行输入一个整数 $T$，表示测试用例的数量。 每个测试用例的第一行包含两个空格分隔的整数 $N$ 和 $K$，表示音符的数量和替换音符的成本。 接下来一行，包含 $N$ 个整数，代表小然的原始歌曲的音符。 ### 输出格式 对于每个测试用例，输出一行，表示使得小然的歌曲满足条件的最小代价。 ### 样例输入 ```text 3 3 2 1 1 1 4 2 3 1 2 4 5 2 1 1 2 2 3 ``` ### 样例输出 ```text 2 0 0 ``` ### 说明 在第一个测试用例中，小然的原始歌曲的音符为 $[1, 1, 1]$，有两个相邻的音符是相同的。他可以选择将第二个音符替换为一个新音符，例如 $2$，这样得到的新歌曲的音符为 $[1, 2, 1]$，满足了条件。这种操作的成本为 $2$，因此最小代价为 $2$。 在第二个测试用例中，小然的原始歌曲的音符为 $[3, 1, 2, 4]$，已经满足了条件，因此最小代价为 $0$。 在第三个测试用例中，小然的原始歌曲的音符为 $[1, 1, 2, 2, 3]$，有两个相邻的音符是相同的。但是他可以将音符重新排列为 $[1, 2, 1, 2, 3]$，这样得到的新歌曲的音符满足了条件，且重新排列的操作是免费的，因此最小代价为 $0$。 ### 评测数据范围 $1 \leq T \leq 10^5$。 $1 \leq N \leq 10^5$。 $1 \leq K \leq 10^9$。 $1 \leq A_i \leq N$。 保证每个测试用例 $N$ 的总和不超过 $5 \times 10^5$。