说明

时间限制：1 Sec 内存限制：256 MB 输入文件：two.in 输出文件：two.out

给定一个长度为 $n$ 的整数数组 $a$ 和一个整数 $k$，如果一个编号 $i$（$1 \le i \le n-k$）满足以下要求：

对于长度为 $k+1$ 的子数组 $[a_i,a_{i+1},\cdots,a_{i+k}]$，将第一个元素乘以 $2^0$，第二个元素乘以 $2^2$，……，第 $k$ 个元素乘以 $2^k$ 之后，子数组严格递增。即，$a_i \times 2^0 \lt a_{i+1} \times 2^1 \lt \cdots \lt a_{i+k} \times 2^k$。

那就说这个编号 $i$ 能支持与 $2$ 相关的排序。

请问，数组 $a$ 中有多少个编号 $i$ 能支持与 $2$ 相关的排序？

输入格式

第一行为一个整数 $t$，表示有 $t$ 组询问；

接下来为 $t$ 组输入，第 $i$ 组输入对应第 $i$ 组询问，每组输入包含两行：

第一行为空格分隔的两个整数 $n$、$k$；

第二行为空格分隔的 $n$ 个整数 $a_1$、$a_2$、……、$a_n$。

输出格式

$t$ 行，第 $i$ 行为对第 $i$ 组询问的回答，为一个整数。

样例

样例 1

6
4 2
20 22 19 84
5 1
9 5 3 2 1
5 2
9 5 3 2 1
7 2
22 12 16 4 3 22 12
7 3
22 12 16 4 3 22 12
9 3
3 9 12 3 9 12 3 9 12

2
3
2
3
1
0

样例说明：

在第 $1$ 组询问中，有 $2$ 个编号满足要求：

$i$ 为 $1$，子数组 $[a_1,a_2,a_3]=[20,22,19]$ 满足 $20 \times 2^0 \lt 22 \times 2^1 \lt 19 \times 2^2$

$i$ 为 $2$，子数组 $[a_2,a_3,a_4]=[22,19,84]$ 满足 $22 \times 2^0 \lt 19 \times 2^1 \lt 84 \times 2^2$

在第 $2$ 组询问中，有 $3$ 个编号满足要求：

$i$ 为 $1$，子数组 $[a_1,a_2]=[9,5]$ 满足 $9 \times 2^0 \lt 5 \times 2^1$

$i$ 为 $2$，子数组 $[a_2,a_3]=[5,3]$ 满足 $5 \times 2^0 \lt 3 \times 2^1$

$i$ 为 $3$，子数组 $[a_3,a_4]=[3,2]$ 满足 $3 \times 2^0 \lt 2 \times 2^1$

而当 $i$ 为 $4$ 时，子数组 $[a_4,a_5]=[2,1]$ 不满足 $2 \times 2^0 \lt 1 \times 2^1$，所以这个子数组不满足条件。

数据范围

$1 \le t \le 10^4$

$3 \le 3 \le n \le 2 \times 10^5$

$1 \le k \le n$

$1 \le a_i \le 10^9$

题目保证所有询问的 $n$ 之和不超过 $2 \times 10^5$