题目描述

给定一个长度为 $n$ 的数组 $a$ 和一个整数 $k$，求出索引 $i(1≤i≤n−k)$ 的数量，使得长度为 $k+1$（而不是长度为 $k$）的子数组 $[a_i,…,a_{i+k}]$ 具有以下性质：

如果第一个元素乘以 $2^0$，第二个元素乘以 $2^1$，……，将第 $(k+1)$ 个元素乘以 $2^k$，则该子数组按严格递增顺序排序。

更公式化地说，计算指数 $i(1≤i≤n−k)$ 的数量，使 $2^0⋅a_i<2^1⋅a_{i+1}<2^2⋅a_{i+2}<……<2^k⋅a_{i+k}$。

输入格式

第一行包含整数 $t(1≤t≤1000)$ 表示测试用例数。

每个测试用例的第一行包含两个整数 $n,k(3≤n≤2⋅10^5，1≤k<n)$ 表示数组的长度和需满足不等式的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,…,a_n(1≤a_i≤10^9)$ 表示数组元素。

所有测试用例的 $n$ 之和不超过 $2⋅10^5$。

输出格式

对于每个测试用例，输出一个整数，表示满足要求的索引数。

测试样例

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

样例说明

在第一个测试用例中，两个子数组都满足以下条件：

$i=1$：子数组 $[a_1,a_2,a_3]=[20,22,19]，1⋅20<2⋅22<4⋅19$。

$i=2$：子数组 $[a_2，a_3，a_4]=[22，19，84]，1⋅22<2⋅19<4⋅84$。

在第二个测试用例中，三个子数组满足以下条件：

$i=1$：子数组 $[a_1,a_2]=[9,5]$，且 $1⋅9<2⋅5$。

$i=2$：子数组 $[a_2,a_3]=[5,3]$，且 $1⋅5<2⋅3$。

$i=3$：子数组 $[a_3,a_4]=[3,2]$，且 $1⋅3<2⋅2$。

$i=4$：子数组 $[a_4,a_5]=[2,1]$，但 $1⋅2=2⋅1$，因此该子数组不满足条件。