题目描述

给定一个长度为 $n$ 的数组 $a$ 和一个整数 $k$，执行如下操作 $k$ 次：

• 对于每个元素 $a_i$，令 $a_i$ 的值为 $\operatorname{mex}(a_1,a_2,...,a_{i-1},a_{i+1},a_{i+2},...,a_n)$。即：令 $a_i$ 的值为其他所有元素的 $\operatorname{mex}$。该计算是对所有元素同时进行的。

请计算数组在 $k$ 次操作之后所有元素之和。

对于整数集合 $d=\{d_1,d_2,...d_n\}$，$\operatorname{mex}(d)$ 定义为最小的且不包含在 $d$ 中的非负整数。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例数量 $t$，满足 $t \leq 10^4$。接下来，对于各个测试用例：

• 第一行包含两个整数 $n$ 和 $k$，表示数组 $a$ 元素个数以及操作次数。保证 $2 \leq n \leq 2\times10^5$ 且 $1 \leq k \leq 10^9$；
• 第二行包含 $n$ 个整数，依次表示 $a_1,a_2,...a_n$，保证对于任意 $a_i$ 有 $0 \leq a_i \leq n$。

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

输出格式

每个测试用例一行，输出 $k$ 次操作之后所有元素的和。

样例

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

3
1
8
25
0

样例说明

对于第一个测试用例，在数组 $[0,2,1]$ 上执行三次操作。第一次操作的结果如下：

• 第一个元素变为 $\operatorname{mex}(2,1)=0$；
• 第二个元素变为 $\operatorname{mex}(0,1)=2$；
• 第三个元素变为 $\operatorname{mex}(0,2)=1$；

故第一次操作后，数组 $[0,2,1]$ 仍然变为 $[0,2,1]$。可以看出不论操作多少次，数组均不会发生变化。所以三次操作后的最终结果仍为 $[0,2,1]$，总和为 $0+2+1=3$。

对于第三个测试用例，数组变为 $[2,2,2,2]$。

来源

Codeforces 2137E，英文题名 Mexification。