$mex(S)$ là số nguyên không âm nhỏ nhất không thuộc tập hợp $S$.

Một xâu con của xâu $X$ là một phần liên tiếp của $X$ có độ dài từ $0$ trở lên.

Gọi xâu MEX là một xâu có độ dài từ $0$ trở lên trong đó các ký tự 'M', 'E', 'X' xuất hiện luân phiên theo đúng thứ tự. Ví dụ, "", "M", "MEX", "MEXME" là các xâu MEX, trong khi "MMEX", "EXM", "EX" thì không phải.

Điểm số của một tập hợp $S$ các xâu được định nghĩa là $mex(|k| : k \in S)$.

Cho độ dài $N$ của một xâu MEX $M$, hãy in ra điểm số lớn nhất có thể đạt được của một tập hợp các xâu con của $M$ sao cho các xâu con này là các xâu MEX và không chồng lấn lên nhau. Việc các xâu con không chồng lấn có nghĩa là mỗi ký tự của $M$ thuộc về tối đa một xâu con.

Input

Dòng đầu tiên chứa số lượng bộ dữ liệu $T$ ($1\leq T\leq 100\,000$).

Dòng đầu tiên của mỗi bộ dữ liệu chứa độ dài $N$ của xâu MEX $M$ ($1\leq N\leq 10^{18}$).

Output

Với mỗi bộ dữ liệu, in ra điểm số lớn nhất của tập hợp.

Ví dụ

Dữ liệu vào 1

5
1
3
4
8
324513245432

Dữ liệu ra 1

2
2
3
4
805621