明明同学喜欢收集木棍，在过去的一年中，明明同学共收集到n根木棍，第i根木棍的长度为ai。今天，明明同学想切割木棍，他可以任意选择一根长度为x的木棍，将其切割为长度为正整数y和z的两根（x,y,z > 0，y+z=x）。为了增加难度，他希望切割后得到的所有木棍都能满足以下条件：

（1）     任选两根木棍，长度分别为x，y（x<=y）;

（2）     确保：2x>y

简而言之就是，任意一根木棍长度的两倍都严格大于所有其他木棍的长度。

请问，明明同学至少需要进行几次切割才可以实现他的目标？

第一行只有一个整数t(1≤t≤100)：测试用例的数量。

每个测试用例的第一行只有一个整数：n（1≤n≤100）：明明同学收集到的木棍数量。

每个测试用例的第二行共有n个整数a1,a2,a3,……,an(1≤ai≤1e7)：n根木棍的初始长度，ai为第i根木棍的长度。

共t行，每个测试用例一行一个整数：最少切割次数。

第一个测试用例中，因为第1根木棍的长度为1，为满足条件2，只能将其他所有木棍都切割成长度为1的木棍，共需要的最小切割次数为：0+1+2+3+4=10次；

在第二个测试用例中，只有一根木棍，不需要切割，所以切割次数为0次；

在第三个测试用例中，明明同学可以将1300切成600+700，将2000切割成1000+1000，将2550切割成1000+1000+550，此时长度最小值为550，2*550=1100，所有其他木棍的长度都严格小于1100。此时，共需要切割4次。我们无法找到比4次更小的切割方案了。