$mex(S)$ — это наименьшее неотрицательное целое число, не содержащееся в множестве $S$.

Подстрокой строки $X$ называется непрерывная последовательность символов $X$ длиной $0$ или более.

Назовем MEX-строкой строку длиной $0$ и более, в которой символы 'M', 'E', 'X' чередуются в указанном порядке. Например, "", "M", "MEX", "MEXME" являются MEX-строками, в то время как "MMEX", "EXM", "EX" и другие таковыми не являются.

Определим оценку множества $S$, состоящего из строк, как $mex(|k| : k \in S)$.

Дана длина $N$ MEX-строки $M$. Найдите максимально возможную оценку множества, которое можно составить, выбрав непересекающиеся подстроки строки $M$, являющиеся MEX-строками. Условие того, что подстроки не пересекаются, означает, что каждый символ строки $M$ может принадлежать не более чем одной выбранной подстроке.

В первой строке задано количество тестов $T$ ($1 \leq T \leq 100\,000$).

В первой строке каждого теста задана длина $N$ MEX-строки $M$ ($1 \leq N \leq 10^{18}$).

Для каждого теста выведите максимально возможную оценку множества.

Примеры

Входные данные 1

5
1
3
4
8
324513245432

Выходные данные 1

2
2
3
4
805621