$mex(S)$ 定義為不包含在集合 $S$ 中的最小非負整數。

字串 $X$ 的子字串是指 $X$ 中長度大於或等於 $0$ 的連續部分。

我們稱一個長度大於或等於 $0$ 的字串為 MEX 字串，若該字串中 'M'、'E'、'X' 依序循環出現。例如：""、"M"、"MEX"、"MEXME" 皆為 MEX 字串，而 "MMEX"、"EXM"、"EX" 則不是。

對於一個由字串組成的集合 $S$，其分數定義為 $mex(|k| : k \in S)$。

給定一個長度為 $N$ 的 MEX 字串 $M$，請輸出透過選擇 $M$ 中互不重疊的 MEX 字串子字串所能組成的集合之最大分數。所謂 $M$ 的子字串互不重疊，是指 $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