404401: GYM101498 F Cooking Time

While cooking your dinner, you will need n ingredients. Initially, all ingredients are in the refrigerator.

You are not allowed to keep more than k ingredients outside the refrigerator at the same time. If there are k ingredients outside the refrigerator, and you need to use another ingredient from it, then you must do the following:

1. Open the refrigerator.
2. Return an ingredient that is currently outside.
3. Take the required ingredient.

Whenever you need an ingredient, you will open the refrigerator only if it's not outside. Each time you open the refrigerator you can take only one item. Your task is to minimize the number of times you will need to open the refrigerator.

The first line contains an integer T (1  ≤  T  ≤  100), where T is the number of test cases.

Each case contains two lines. The first line contains two integers n and k (1  ≤  n, k  ≤  10⁵), the number of ingredients needed, and the maximum allowed number of ingredients that can be kept outside the refrigerator at the same time.

The second line contains n integers a₁, a₂, ..., a_n (1  ≤  a_i  ≤  10⁹), where a_i is the ID of the i^th ingredient you will need. Ingredients must be used in the order given in the input.

For each test case, print a single integer that represents the minimum number of times you will open the refrigerator.

2
5 3
2 4 5 2 1
7 3
1 2 3 4 3 2 1

4
5

In the first test case, you can keep up to 3 items outside the refrigerator. You must open the refrigerator 3 times to use the first three ingredients (2, 4, and 5), and then keep them outside the refrigerator. The fourth ingredient (2) is already outside the refrigerator, so you can use it directly. You cannot use the fifth item because there are 3 items outside the refrigerator, so you must open the refrigerator, return an item, and take the fifth ingredient from the refrigerator and use it.