给定长度为 $n$ 的数组 $a$ 和一个整数 $k$。 你需要重复执行如下操作共 $k$ 次：

对每个元素 $a_i$，将 $a_i$ 重新赋值为去掉自身后其余所有元素的 $\text{mex}$ 值。 也就是：

$$a_i \leftarrow \text{mex}(a_1,a_2,\dots,a_{i-1},a_{i+1},\dots,a_n) $$

所有元素的更新同时进行。

求经过 $k$ 次操作后，数组所有元素的和。

---

定义

整数集合 $d_1,d_2,\dots,d_k$ 的 $\text{mex}$ 定义为： 集合中没有出现的最小非负整数。

---

输入

多组测试数据。 第一行一个整数 $t$（$1\le t\le 10^4$），表示测试组数。

每组数据： 第一行两个整数 $n,k$（$2\le n\le 2\cdot 10^5,\ 1\le k\le 10^9$），分别表示数组长度和操作次数。 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$（$0\le a_i\le n$）。

保证所有测试数据的 $n$ 总和不超过 $2\cdot 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]$。 第一次操作：

• 第一个元素：$\text{mex}(2,1)=0$
• 第二个元素：$\text{mex}(0,1)=2$
• 第三个元素：$\text{mex}(0,2)=1$

操作后数组保持 $[0,2,1]$ 不变。 无论再执行多少次操作，数组都不会变化，执行 $3$ 次后总和仍为 $0+2+1=3$。

第三组测试执行一次操作后，数组变为 $[2,2,2,2]$，总和为 $8$。