该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem Background

Muxue won a silver medal in NOI 2077 and will receive a preferential admission policy (Category II Strong Foundation Program) from Peking University.

Don't leave me here in the dark where it's hard to see
Show me your heart
Shed a light on me

"With bitterness and joy, writing life, a brilliant tomorrow."

Problem Description

NOI 2077 was successfully held at the Affiliated High School of Shanghai Fudan Middle School Education Group. The exciting award ceremony has arrived.

However, the organizers encountered a problem: the score set above the bronze medal cutoff only has 11 distinct values. If participants were to go on stage strictly by score, many contestants with the same score would appear together. Contestants always prefer to go on stage closer to the high-score segment. Therefore, the organizers decided to arrange contestants with the same score by their height.

To avoid any appearance of height discrimination, the organizers decided that the height of the i-th contestant to go on stage is a_i. The contestants are divided into k groups to go on stage sequentially. Each group must be a contiguous subsequence of the array a, all contestants must go on stage to receive their award, and each contestant can only go on stage once. The organizers define the non-uniformity of such a grouping as the maximum number of inversions in any group. The number of inversions in an array b of length m is the number of ordered pairs (i, j) such that 1 ≤ i < j ≤ m and b_i > b_j.

For T groups of contestants with the same score, find the minimum possible non-uniformity.

Input Format

The first line contains an integer T, the number of test cases.

For each test case:

• The first line contains two integers n, k, representing the number of contestants with the same score and the number of groups.
• The second line contains n integers a_i, representing the heights of the contestants in the order they are to go on stage.

Output Format

Output T lines. For each test case, output one integer representing the minimum possible non-uniformity.

Sample Input/Output 1

Input

1
10 3
-375380000 436055029 -925293020 454128611 -171710176 753457200 55606397 159950341 49081304 -993551231

Output

2

Data Scale and Constraints

This problem uses bundled testing.

Let N = Σn (the sum of all n across test cases).

Subtask 1 (22 points): N ≤ 10

Subtask 2 (14 points): N ≤ 300

Subtask 3 (26 points): N ≤ 5000

Subtask 4 (20 points): N ≤ 5 × 10^4

Subtask 5 (18 points): No additional constraints

For all test data:1 ≤ T ≤ 10^5, 1 ≤ k ≤ n ≤ 10^5, |a_i| ≤ 10^9, 1 ≤ N ≤ 10^5.