您将获得 已排序 整数数组 $$$[a_1, a_2, \dots, a_n]$$$。我们可以对此数组执行任意数量的以下类型的操作:
- 标记数组的第一个元素,以及不等于其左邻居的所有元素(即,满足 $$$a_i \ne a_{i-1}$$$ 的所有元素 $$$i$$$)。
- 然后删除所有标记的元素或复制它们(即,用两个相同的元素替换每个标记的元素)。
例如,考虑数组 $$$[\mathbf{1}, 1, 1, \mathbf{2}, \mathbf{4}, 4, \mathbf{5}]$$$ (标记的元素以粗体显示)。如果我们删除所有标记的元素,我们会得到 $$$[1, 1, 4]$$$,如果我们复制它们,我们会得到 $$$[1, 1, 1, 1, 2, 2, 4, 4, 4, 5, 5]$$$。
如果数组变空,则无法执行操作。每次操作后,每个元素都会被取消标记。
如果一个整数数组 $$$b$$$ 可以通过一定数量的所描述的操作从数组 $$$a$$$ 中获得,那么我们称该数组 $$$b$$$ 是可达的。您的任务是计算长度为 $$$k$$$ 的可达数组的数量。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例由两行组成:
- 第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 3 \cdot 10^5$$$);
- 第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_1 \le a_2 \le \dots \le a_n \le n$$$)。 请注意,数组已排序。
对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 — 长度为 $$$k$$$ 的可达数组 $$$b$$$ 的数量。可以证明,在问题的约束下,答案符合标准的 $$$32$$$ 位整数类型。
示例
输入复制
101 514 51 1 2 23 11 1 14 81 2 3 48 61 1 1 2 2 2 2 26 31 1 2 2 3 310 71 1 1 2 2 3 3 3 3 412 51 1 1 1 2 2 2 3 3 4 4 46 51 1 2 2 3 33 11 2 2
输出复制
1011212101
注意
在第一个示例中,可以执行以下操作序列:
- $$$[\mathbf{1}] \rightarrow [\mathbf{1}, 1] \rightarrow [\mathbf{1}, 1, 1] \rightarrow [\mathbf{1}, 1, 1, 1] \rightarrow [1, 1, 1, 1, 1]$$$。
在第二个示例中,不可能获得长度为 $$$5$$$ 的数组。
在第三个示例中,可以执行以下操作序列:
- $$$[\mathbf{1}, 1, 1] \rightarrow [\mathbf{1}, 1] \rightarrow [1]$$$。
在第五个例子中,可以得到数组$$$[1, 1, 2, 2, 2, 2]$$$和$$$[2, 2, 2, 2, 2, 2]$$$:
- $$$[\mathbf{1}, 1, 1, \mathbf{2}, 2, 2, 2, 2] \rightarrow [1, 1, 2, 2, 2, 2]$$$;
- $$$[\mathbf{1}, 1, 1, \mathbf{2}, 2, 2, 2, 2] \rightarrow [\mathbf{1}, 1, \mathbf{2}, 2, 2, 2] \rightarrow [\mathbf{1}, \mathbf{2}, 2, 2] \rightarrow [\mathbf{2}, 2] \rightarrow [\mathbf{2}, 2, 2] \rightarrow [\mathbf{2}, 2, 2, 2] \rightarrow [\mathbf{2}, 2, 2, 2, 2] \rightarrow [2, 2, 2, 2, 2, 2]$$$。
在第七个例子中,可以获得数组$$$[1, 1, 1, 3, 3, 3, 3]$$$和$$$[3, 3, 3, 3, 3, 3, 3]$$$。