DragonEmperor village is at war. DragonEmperor has a very evil strategy. He planned to send few boxes to his enemy as a "token of peace". In actual these boxes are full of destructive material.
DragonEmperor has N boxes with him. Each box has a size (integer number). A box can be placed into another box if and only if the size of outer box which hold the smaller box is at least twice as large as the size of box which is held inside it.
Also each box can hold at most one box, otherwise enemy may get an hint by the weight of boxes that something is wrong. Also box which is held inside another box cannot hold any boxes inside it.
His troops packed the boxes one inside another in such a way that the box which is held inside bigger box cannot be visible from outside.
He need to make other war strategies , so he needs your help to form the minimal number of boxes that will be visible at end.
Input Format :
First line contains number of test cases T. First line of each test case contains N, denoting total number of boxes available at start. Each of the next N lines contains an integer Si — the size of the i-th box (1 ≤ i ≤ N)
Output Format :
For each test case, you need to help DragonEmperor find the minimal number of boxes that will be visible at end.
Constraints :
1 ≤ T ≤ 10
1 ≤ N ≤ 105
Size of each box, Si lies between 1 ≤ Si ≤ 105 for all 1 ≤ i ≤ N
DIFFICULTY : Easy Problem Setter : Gaurav Gupta
There can be multiple possibilities, here one of the possibility for first test case is as follow :
- 1 Box of size 2 contained in Box of size 6
- 1 Box of size 2 contained in Box of size 7
- 1 Box of size 4 contained in Box of size 8
And remaining two boxes of size 5 and 9 remain single. So total 5 boxes will be visible at the end.
For second test case, arrangement can be like this :
- 1 Box of size 2 contained in Box of size 6
- 1 Box of size 2 contained in Box of size 7
And remaining three boxes of size 5,5 and 9 remain single. So total 6 boxes will be visible at the end.
