2087 年，人工智能已经解决了那些从未被提出过的超图着色问题，而建成的超回路（Hyperloop）网络却成了世界上最慢的地铁。H 题中开发的软件在过去 10 年里一直运行得完美无缺，但（一如既往地）社会学方面成了该计划中最薄弱的环节：每当系统提出一条涉及尽可能长连接的超回路路线时，看着行程表的乘客血压升高得太厉害，以至于他们不再需要以高价购买 Melon 的咖啡了。

为了安抚投资者，Usk 决定展示公司的财务业绩。不幸的是，由于低门票收入和高昂的咖啡采购成本，业绩并不太令人印象深刻。这位古怪的亿万富翁决定对这些数字进行一点“微调”。

公司的业绩可以用一个包含 $n$ 个数字的序列来表示，代表随后几个月的收入。为了不引起怀疑，Usk 决定将序列中选定的连续区间内的数字增加某个正整数。执行一次该操作未能达到这位远见卓识者的期望。于是他尝试了第二次、第三次……最终，他决定最多执行 $k$ 次增加业绩的操作（每次增加的数值可以不同）。

Usk 知道，投资者主要关注公司收入的增长，而他们不喜欢收入相比之前取得的业绩出现下降。因此，他希望最小化其财务结果中的逆序对数量。你能拯救他公司的未来吗？

输入格式

输入的第一行包含测试用例的数量 $z$ ($1 \le z \le 400$)。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n, k$ ($1 \le n \le 6000, 0 \le k \le n$)。

第二行包含一个数字序列 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$)，表示 Melon 公司的财务业绩。

所有测试用例的 $n$ 之和不超过 6000。

输出格式

对于每个测试用例，输出一个整数，表示在执行不超过 $k$ 次增加连续区间数字的操作后，序列中逆序对的最小数量。

样例

输入 1

2
6 1
4 5 6 2 2 1
6 2
4 5 6 2 2 1

输出 1

2
0

说明

注：给定一个序列 $a_1, a_2, \dots, a_n$，逆序对是指满足 $i < j$ 且 $a_i > a_j$ 的下标对 $(i, j)$。