Longest Increasing Subsequence with Slot Limit

You are given a sequence of coins where each coin is marked with a year. Due to limited space, you can only select at most \(K\) coins to arrange in strictly increasing order based on their inscription years. Your task is to compute the length of the longest strictly increasing subsequence that does not exceed the available \(K\) slots.

Formally, given an array \(A\) of \(N\) integers and an integer \(K\), find the length \(L\) of the longest strictly increasing subsequence in \(A\), and output \(\min(L, K)\).

Note: The subsequence does not have to be contiguous.

inputFormat

The first line of input contains an integer \(T\) representing the number of test cases. Each test case consists of two lines:

• The first line contains two space-separated integers \(N\) and \(K\), where \(N\) is the number of coins and \(K\) is the maximum number of slots available.
• The second line contains \(N\) space-separated integers representing the years inscribed on the coins.

\(1 \leq T \leq 100\), \(1 \leq N \leq 10^3\).

outputFormat

For each test case, output a single integer on a new line — the length of the longest strictly increasing subsequence that can be placed into the \(K\) available slots (i.e., \(\min(\text{LIS}, K)\)).

## sample

1
6 4
1970 1980 1990 2000 1940 1950

4

</p>