$mex(S)$ to najmniejsza nieujemna liczba całkowita, która nie należy do zbioru $S$.

Podciąg (substring) ciągu $X$ to ciągły fragment $X$ o długości co najmniej $0$.

Nazywamy ciąg MEX ciągiem o długości co najmniej $0$, w którym znaki 'M', 'E', 'X' występują naprzemiennie w tej kolejności. Na przykład "", "M", "MEX", "MEXME" są ciągami MEX, natomiast "MMEX", "EXM", "EX" nie są ciągami MEX.

Wynik zbioru $S$ składającego się z ciągów definiujemy jako $mex(|k| : k \in S)$.

Mając dany ciąg MEX $M$ o długości $N$, wypisz maksymalny wynik zbioru, który można utworzyć poprzez wybranie nieprzecinających się podciągów ciągu $M$, będących ciągami MEX. To, że podciągi $M$ nie przecinają się, oznacza, że każdy znak ciągu $M$ należy do co najwyżej jednego wybranego podciągu.

Wejście

W pierwszej linii podana jest liczba przypadków testowych $T$ ($1\leq T\leq 100\,000$).

W pierwszej linii każdego przypadku testowego podana jest długość $N$ ciągu MEX $M$ ($1\leq N\leq 10^{18}$).

Wyjście

Dla każdego przypadku testowego wypisz maksymalną wartość wyniku zbioru.

Przykład

Przykład 1

5
1
3
4
8
324513245432

Wyjście 1

2
2
3
4
805621