LearnToCP
Sign in
Navigation
HomeRoadmapProblemsAbout Us
Theory
Contest Knowledge
Selecting an IDE
Basics
Your First ProgramData types and IOC++ syntaxModuloFunctionsVectorsMatricesTime Complexity
Sorting
SortingCounting sortRadix Sort
Optimization Techniques
Two PointersSum of numbers 1 to nPrefix sumBinary SearchGreedyBinary Search FunctionsBinary Search by AnswerDivide and Conquer
Binary Numbers
Binary NumbersNumbers in codeBitwise OperationsBitmasks
Math
Binary ExponentiationPrime NumbersPrime FactorizationGCD and LCMSieve of EratosthenesModified Sieve
Data Structures
StringsStackQueueMapsSetsPriority QueueCustom Criteria for FunctionsSegment TreesFenwick TreesSparse TablesUnion Find
Combinatorics
Addition PrincipleMultiplication PrincipleCombinatoric ObjectsInclusion Exclusion Principle
Geometry
Geometry BasicsVectorsCross and Dot ProductLinesPolygonsAnglesPoint in PolygonDistances and Intersection PointsConvex HullCircles
Recursion
PointersRecursionGenerating Combinatoric Objects
Dynamic Programming
About DPTree DPBitmask DPDigit DP
Graph Theory
GraphsDFS and BFSShortest PathsTreesTopological SortingDijkstra's AlgorithmMinimum Spanning TreesShortest Path Algorithms
Advanced Graph Theory
BiconnectivityStrongly Connected ComponentsBipartite GraphGraph FlowAugmenting PathsFlow - Minimum Cut DualityHeavy-Light DecompositionCentroid Decomposition
Advanced Data Structures
2D and 3D Segment TreesLazy PropagationImplicit Segment TreesPersistent Segment TreesLowest Common AncestorTrieBalanced Binary Search TreesMo's Algorithm

H-Index

EasyProblem #32
Time LimitMemoryInputOutput
1 s64 MBstdinstdout

Scientists are ranked by a statistic called the Hirsch index (h-index for short). The h-index of a scientist is the largest number h such that the scientist has at least h papers with at least h citations each. Given the citation counts of all papers of a scientist, your task is to compute their h-index.

Input

First line of input will be a single integer t - the number of testcases.
Each testcase consists of two lines:

  • the first contains an integer n - the number of papers,
  • and the second contains n integers - the number of citations of each paper.

Output

For every testcase print a single line with the h-index.

Example

Input
2
8
3 5 12 7 5 9 0 17
3
0 0 0
Output
5
0

In the first testcase there are exactly 5 papers with at least 5 citations (5,12,7,9,17), but not 6 papers with at least 6 citations. In the second no paper has even one citation, so the h-index is 0.

Constraints

1≤t≤1000
1≤n≤2⋅105
0≤ai​≤109
n1​+n2​+…+nt​≤2⋅105


This problem was adapted, with permission, from Hiršov h-indeks, authored by Društvo matematičara Srbije and Fondacija Petlja.

Submit your solution

Sign in to submit your solution and track your progress.

Sign in to submit