C. Level Up
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ positive integers.

Consider partitioning the array into exactly $$$k$$$ non-empty contiguous segments, such that each element belongs to exactly one segment.

For a segment $$$[l, r]$$$, its contribution is the number of indices $$$i$$$ ($$$l \le i \le r$$$) such that $$$a_i \gt a_j$$$ for all $$$l \le j \lt i$$$. In other words, an element contributes if it is strictly greater than every previous element in the same segment.

For example, the contribution of the segment $$$[3, 1, 4, 2, 5]$$$ is $$$3$$$; the contributing elements are $$$3$$$, $$$4$$$, and $$$5$$$.

Your task is to divide the array into exactly $$$k$$$ non-empty contiguous segments such that the sum of contributions of all segments is maximized.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^6$$$, $$$1 \le k \le \min(n, 100)$$$) — the length of the array and the number of segments.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, print a single integer — the maximum possible total contribution after dividing the array into exactly $$$k$$$ non-empty contiguous segments.

Example
Input
4
5 1
1 3 2 5 4
5 2
1 3 2 5 4
6 3
5 4 3 2 1 6
4 4
7 7 7 7
Output
3
4
4
4
Note

In the first test case, there is only one segment: $$$[1, 3, 2, 5, 4].$$$ The contributing elements are $$$1$$$, $$$3$$$, and $$$5$$$, so the contribution is $$$3$$$.

In the second test case, an optimal division into segments is $$$[1, 3] \mid [2, 5, 4].$$$ The first segment contributes $$$2$$$ and the second segment contributes $$$2$$$, giving a total contribution of $$$4$$$.

In the third test case, one optimal way to divide the array is $$$[5] \mid [4] \mid [3, 2, 1, 6].$$$ The contributions of the three segments are $$$1$$$, $$$1$$$, and $$$2$$$, respectively, so the answer is $$$4$$$.