| Codeforces Round 599 (Div. 2) |
|---|
| Закончено |
Уджан решил сделать новую крышу для своего дома. У него есть $$$n$$$ прямоугольных досок, пронумерованных числами $$$1$$$ до $$$n$$$. У $$$i$$$-й доски размеры $$$a_i \times 1$$$ (то есть ширина равна $$$1$$$, а высота равна $$$a_i$$$).
В данный момент Уджан хочет сделать квадратную крышу. Сначала он выберет некоторые доски и расположит их одну за другой в каком-то порядке. Затем он склеит все эти доски по их вертикальным сторонам. Наконец, он вырежет квадрат из получившейся фигуры таким образом, что стороны квадрата горизонтальны и вертикальны.
Например, если у Уджана есть доски с длинами $$$4$$$, $$$3$$$, $$$1$$$, $$$4$$$ и $$$5$$$, он может выбрать доски с длинами $$$4$$$, $$$3$$$ и $$$5$$$. Тогда он может вырезать квадрат размером $$$3 \times 3$$$, который является наибольшим возможным. Учтите, что в данном случае это не единственный способ получить квадрат размером $$$3 \times 3$$$.
Чему равняется наибольшая длина стороны квадрата, который может получить Уджан?
Первая строка ввода содержит одно целое число $$$k$$$ ($$$1 \leq k \leq 10$$$) — количество наборов входных данных в тесте.
Для каждого набора входных данных первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 1\,000$$$) — количество досок в запасе Уджана. Следующая строка содержит $$$n$$$ целых чисел $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — длины досок.
Для каждого набора входных данных выведите одно целое число, наибольшую возможную длину стороны квадрата.
4 5 4 3 1 4 5 4 4 4 4 4 3 1 1 1 5 5 5 1 1 5
3 4 1 3
Первый набор входных данных примера соответствует примеру из условия.
Во втором наборе входных данных примера, склеив все $$$4$$$ доски, получается квадрат размером $$$4 \times 4$$$.
В третьем наборе входных данных примера наибольший квадрат имеет размер $$$1 \times 1$$$ и такой можно получить, просто взяв любую из досок.
