Brian sabe que. El palíndromo es una cadena que se puede leer de la misma manera , de izquierda a derecha y de derecha a izquierda. Por ejemplo, las cadenas "aaaaa", "1221", "bbaabb" son palíndromos, sin embargo la cadena "coder" no es un palíndromo, porque si lo leemos de derecha a izquierda, obtendremos "redoc" que no es lo mismo que "coder".

Llamamos a una cadena de "doble cadena" si tiene una longitud uniforme y la primera mitad de esta cadena es igual a la segunda mitad de esta cadena, por ejemplo " abab " es una doble cadena porque la primera mitad "ab" es igual que la segunda mitad "ab", sin embargo la cadena "abba" no es una doble cadena porque la primera mitad "ab" no es igual a la segunda mitad "ba". La cadena vacía "" es una doble cadena, y su longitud es de 0.

A Brian no le gustan los palíndromos, sin embargo le gustan las "cadenas dobles". A menudo le gusta cambiar el orden de las letras de algun "palíndromo" y/o a veces eliminar algunos de los carácteres de la misma a fin de convertirla en "doble cadena". Ahora se pregunta: si se le da un palíndromo de longitud N, ¿Cuál es el máximo número de caracteres de una "doble cadena" que se pueda obtener mediante la eliminación y/o cambiando el orden de los carácteres en ella?.

Input

La primera línea del INPUT comienza con un número M que indica el número de casos del problema propuesto. (1 <= M <= 100)

Cada caso está compuesto de la(s) siguiente(s) linea(s):

N : La longitud del palíndromo que se le da a Brian ( 1<= N <=1000000000 )

Output

La cantidad de caráteres de la doble cadena que se puede obtener del palíndromo de longitud N.

Entrada de ejemplo