LearnToCP
Sign in
Navigation
HomeRoadmapProblemsAbout Us
Theory
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 Functions
Binary Numbers
Binary NumbersNumbers in codeBitwise Operations
Math
Binary ExponentiationPrime NumbersPrime FactorizationGCD and LCMSieve of Eratosthenes
Data Structures
StringsStackQueue
Dynamic Programming
About DPDP problems

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