## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] 2^Sort Codeforces Solution | Codeforces Problem Solution 2022

G. 2^Sort
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array $a$ of length $n$ and an integer $k$, find the number of indices $1\le i\le n-k$ such that the subarray $\left[{a}_{i},\dots ,{a}_{i+k}\right]$ with length $k+1$ (not with length $k$) has the following property:

• If you multiply the first element by ${2}^{0}$, the second element by ${2}^{1}$, ..., and the ($k+1$)-st element by ${2}^{k}$, then this subarray is sorted in strictly increasing order.
More formally, count the number of indices $1\le i\le n-k$ such that

Input

The first line contains an integer $t$ ($1\le t\le 1000$) — the number of test cases.

The first line of each test case contains two integers $n$$k$ ($3\le n\le 2\cdot {10}^{5}$$1\le k) — the length of the array and the number of inequalities.

The second line of each test case contains $n$ integers ${a}_{1},{a}_{2},\dots ,{a}_{n}$ ($1\le {a}_{i}\le {10}^{9}$) — the elements of the array.

The sum of $n$ across all test cases does not exceed $2\cdot {10}^{5}$.

Output

For each test case, output a single integer — the number of indices satisfying the condition in the statement.