$mex(S)$ est le plus petit entier non négatif qui n'est pas inclus dans l'ensemble $S$.

Une sous-chaîne d'une chaîne $X$ est une partie contiguë de $X$ de longueur supérieure ou égale à $0$.

On appelle chaîne MEX une chaîne de longueur supérieure ou égale à $0$ dans laquelle les caractères 'M', 'E', 'X' apparaissent alternativement dans cet ordre. Par exemple, "", "M", "MEX", "MEXME" sont des chaînes MEX, tandis que "MMEX", "EXM", "EX" ne le sont pas.

Le score d'un ensemble $S$ composé de chaînes est défini par $mex(|k| : k \in S)$.

Étant donné la longueur $N$ d'une chaîne MEX $M$, calculez le score maximal d'un ensemble de sous-chaînes de $M$ qui sont elles-mêmes des chaînes MEX et qui ne se chevauchent pas. Le fait que les sous-chaînes ne se chevauchent pas signifie que chaque caractère de $M$ appartient au plus à une seule sous-chaîne.

Entrée

La première ligne contient le nombre de cas de test $T$ ($1 \leq T \leq 100\,000$).

La première ligne de chaque cas de test contient la longueur $N$ de la chaîne MEX $M$ ($1 \leq N \leq 10^{18}$).

Sortie

Pour chaque cas de test, affichez le score maximal de l'ensemble.

Exemples

Entrée 1

5
1
3
4
8
324513245432

Sortie 1

2
2
3
4
805621