We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Greedy
  4. Team Formation

Team Formation

For an upcoming programming contest, Roy is forming some teams from the students of his university. A team can have any number of contestants.

Roy knows the skill level of each contestant. To make the teams work as a unit, he forms the teams based on some rules. Each of the team members must have a unique skill level for the team. If a member's skill level is where , there exists another team member whose skill level is . Note that a contestant can write buggy code and thus can have a negative skill level.

The more contestants on the team, the more problems they can attempt at a time so Roy wants to form teams such that the smallest team is as large as possible.

For example, there are contestants with skill levels . There are many ways teams could be formed, e.g. [-1], [0],...,[3]. At the other end of the spectrum, we could form and . We're looking for the largest smaller team size though. Two sets that meet the criteria are and . The largest smaller team size possible is .

Note: There is an edge case where contestants have registered. As no teams are to be created, the largest team created will have members.

Input Format

The first line contains an integer , the number of test cases.

Each of the next lines contains a string of space-separated integers, followed by integers , a list of the contestants' skill levels.

Constraints



Output Format

For each test case, print the size of largest possible smallest team on a separate line.

Sample Input

4  
7 4 5 2 3 -4 -3 -5  
1 -4  
4 3 2 3 1  
7 1 -2 -3 -4 2 0 -1

Sample Output

3
1
1
7

Explanation

For the first case, Roy can form two teams: one with contestants with skill levels {-4,-3,-5} and the other one with {4,5,2,3}. The first group containing 3 members is the smallest.

In the second case, the only team is {-4}

In the third case, the teams are {3} , {1,2,3}, the size of the smaller group being 1.

In the last case, you can build one group containing all of the contestants. The size of the group equals the total number of contestants.

Time limits

Time limits for this challenge are given here

Note

If n = 0, print 0.