代码放二楼

描述

给定n个正整数a1,a2,…,an和一个正整数k。

一座高度为k的塔b1,b2,…,bk满足2b1≤b2,2b2≤b3,2b3≤b4,…,2bk−1≤bk。

你要从中选择一些数来叠很多座高度为k的塔，问最多能叠多少座塔。

输入

第一行包含一个正整数T(1≤T≤10)，表示测试数据的组数。

每组数据第一行包含两个正整数n,k(2≤n≤100000,2≤k≤30)。

第二行包含n个正整数a1,a2,…,an(1≤ai≤10^9)。

输出

对于每组数据输出一行一个整数，即能叠出的塔的数量。

输入样例 1

3 4 2 1 2 3 4 6 3 1 1 2 2 4 4 6 3 1 1 2 2 3 4

输出样例 1

2 2 1