Under construction

Still being built. Things may change

Countdown

Interview

Time limit20sMemory limit1024 MB

Summary
Count how many contiguous subarrays of length K equal the descending run K, K-1, ..., 2, 1.
Level

Easy3 of 10

Topics
Array, Sliding window, Implementation
Solved
No attempts yet

Problem

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

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?

Input

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 Ai.

Output

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.

Limits

  • 1 ≤ T ≤ 100.
  • 2 ≤ K ≤ N.
  • 1 ≤ Ai ≤ 2 × 105, for all i.

Hint

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

Examples1

  1. Example 1

    Input
    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
    Expected output
    Case #1: 2
Case #2: 0
Case #3: 1