$mex(S)$ es el entero no negativo más pequeño que no está contenido en el conjunto $S$.

Una subcadena de una cadena $X$ es una parte contigua de $X$ con una longitud de $0$ o más.

Llamamos cadena MEX a una cadena de longitud $0$ o más en la que los caracteres 'M', 'E' y 'X' aparecen alternados en ese orden. Por ejemplo, "", "M", "MEX" y "MEXME" son cadenas MEX, mientras que "MMEX", "EXM" y "EX" no lo son.

Definimos la puntuación de un conjunto $S$ de cadenas como $mex(|k| : k \in S)$.

Dado un número $N$ que representa la longitud de una cadena MEX $M$, calcula la puntuación máxima de un conjunto que se puede formar seleccionando subcadenas de $M$ que sean cadenas MEX y que no se solapen. Que las subcadenas de $M$ no se solapen significa que cada carácter de $M$ está contenido en, a lo sumo, una subcadena.

Entrada

La primera línea contiene el número de casos de prueba $T$ ($1 \leq T \leq 100\,000$).

La primera línea de cada caso de prueba contiene la longitud $N$ de la cadena MEX $M$ ($1 \leq N \leq 10^{18}$).

Salida

Para cada caso de prueba, imprime la puntuación máxima del conjunto.

Ejemplos

Entrada 1

5
1
3
4
8
324513245432

Salida 1

2
2
3
4
805621