题目描述

Avery has an array of $N$ positive integers. The i-th integer of the array is $A_i$.

A contiguous subarray is an $m$-countdown if it is of length $m$ and contains the integers $m, m-1$, $m-2, ..., 2, 1$ in that order. For example, $[3, \;\; 2, \;\; 1]$ is a $3$-countdown.

Can you help Avery count the number of $K$-countdowns in her array?

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case begins with a line containing the integers $N$ and $K$. The second line contains $N$ integers. The i-th integer is $A_i$.

输出格式

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from $1$) and $y$ is the number of $K$-countdowns in her array.

3
12 3
1 2 3 7 9 3 2 1 8 3 2 1
4 2
101 100 99 98
9 6
100 7 6 5 4 3 2 1 100

Case #1: 2
Case #2: 0
Case #3: 1

提示

In sample case #1, there are two 3-countdowns as highlighted below.

• 1 2 3 7 9 3 2 1 8 3 2 1
• 1 2 3 7 9 3 2 1 8 3 2 1

In sample case #2, there are no 2-countdowns.

In sample case #3, there is one 6-countdown as highlighted below.

• 100 7 6 5 4 3 2 1 100

Limits

$1 \le T \le 100$.

$2 \le K \le N$.

$1 \le A_i \le 2 \times 10^5$, for all $i$.

Test Set 1

$2 \le N \le 1000$.

Test Set 2

$2 \le N \le 2 \times 10^5$ for at most $10$ test cases.

For the remaining cases, $2 \le N \le 1000$.