Merge Elements :
Difficulty Level : Medium
Submissions : 682
Asked In :
Marks :10
: 2 | : 5
Given an array X and an integer N. You can perform the following operation on the array elements: for any two elements in the array (a,b) you can merge elements b into a if 2a >= b. The numbers add together if merged.
You have to perform this operation until only one element remains. Return the number of positions possible for the final number.
Constraints:
1 <= t <= 10
1<= N <= 1000000
1 <= Xi <= 10^9
Input
First line contains integer t which is the number of test cases. For each test case:
First line contains an integer N. The next line contains N space separated integers.
Output
For each test case output one integer. corresponding to the number of possible positions.
Examples
Input
1 2 3 4
Output
2
Input
2 4 1 2 3 4 2 1 3
Output
4 1
