$mex(S)$ 定义为不属于集合 $S$ 的最小非负整数。

字符串 $X$ 的子串是指 $X$ 中长度大于等于 $0$ 的连续部分。

称一个长度大于等于 $0$ 的字符串为 MEX 字符串，如果该字符串中 'M', 'E', 'X' 按顺序循环出现。例如，"", "M", "MEX", "MEXME" 是 MEX 字符串，而 "MMEX", "EXM", "EX" 等不是 MEX 字符串。

对于一个由字符串组成的集合 $S$，其分数为 $mex(|k| : k \in S)$。

给定一个 MEX 字符串 $M$ 的长度 $N$，求出从 $M$ 中选择若干互不重叠的 MEX 字符串子串所能构成的集合的最大分数。子串互不重叠意味着 $M$ 中的每个字符最多只能被包含在一个子串中。

第一行包含一个整数 $T$，表示测试用例的数量。($1\leq T\leq 100\,000$)

每个测试用例的第一行包含 MEX 字符串 $M$ 的长度 $N$。($1\leq N\leq 10^{18}$)

对于每个测试用例，输出集合分数的最大值。

样例

输入格式 1

5
1
3
4
8
324513245432

输出格式 1

2
2
3
4
805621