FoniKs busca a Félix

Tiempo máximo: 1000 ms

Memoria máxima: 10000 KB

Dificultad: Medio (45)

¡Félix se ha escapado en el multiverso gatuno!

\(\href{https://algomania.es/account/65}{\color{blue}{\underline{\text{Foniks}}}}\) está en shock y no puede describirte cómo es, solo puede responder a preguntas sencillas de sí o no de la forma \(f_i < x\), donde \(f_i\) es el valor que Félix tiene de la característica \(i\).

Un gato se puede diferenciar en el multiverso gatuno de forma única por \(k\) características, de forma que el gato \(1, 7, 3, 4\) (con \(k = 4\) características) es único. Cada característica \(i\) es un número entero entre \(0\) y \(a_i\) inclusive.

Tu tarea es descubrir el mínimo número \(n\) que te garantice que haciendo máximo \(n\) preguntas puedas diferenciar a Félix de forma única.

Simplemente ¡mira qué guapo es, qué elegancia, qué porte! Ayúdale porque no sobreviviría ni un día solo...

Entrada

La entrada consiste de una primera línea con \(t\) (\(1 \leq t \leq 100\)), el número de casos de prueba. Cada caso de prueba consiste en dos líneas. La primera línea incluye \(k\) (\(1 \leq k \leq 10^5\)) (el número de características diferentes necesarias para diferenciar un gato). La segunda línea incluye \(k\) números, \(a_0, a_1, ..., a_{k-1}\) (\(a_i \leq 10^5\)) (el máximo en esa característica).

Salida

Una línea por cada caso de prueba con \(n\), el mínimo número de preguntas que te garantizan diferenciar a Félix de forma única.

Ejemplos

Ejemplo 1

Entrada

2
5
1 2 3 4 5
3
120 45 2000

Salida

11
24

ID	Usuario	Lenguaje	Veredicto	Tiempo	Memoria	Fecha

#	ID	Usuario	Lenguaje	Veredicto	Tiempo	Memoria	Fecha