$mex(S)$ is the smallest non-negative integer that is not contained in the set $S$.

A substring of a string $X$ is a contiguous part of $X$ with length $0$ or greater.

A string of length $0$ or greater where 'M', 'E', and 'X' appear in alternating order is called a MEX string. For example, "", "M", "MEX", and "MEXME" are MEX strings, while "MMEX", "EXM", and "EX" are not.

The score of a set $S$ consisting of strings is defined as $mex(|k| : k \in S)$.

Given the length $N$ of a MEX string $M$, output the maximum possible score of a set formed by choosing non-overlapping substrings of $M$ that are themselves MEX strings. That the substrings of $M$ are non-overlapping means that every character of $M$ is contained in at most one substring.

Input

The first line contains the number of test cases $T$ ($1 \leq T \leq 100\,000$).

Each test case consists of a single line containing the length $N$ of the MEX string $M$ ($1 \leq N \leq 10^{18}$).

Output

For each test case, output the maximum score of the set.

Examples

Input 1

5
1
3
4
8
324513245432

Output 1

2
2
3
4
805621