$mex(S)$ は、集合 $S$ に含まれない最小の非負整数である。

文字列 $X$ の部分文字列とは、長さが $0$ 以上の $X$ の連続した一部分を指す。

'M', 'E', 'X' がこの順序で交互に現れる長さ $0$ 以上の文字列を MEX 文字列と呼ぶことにする。例えば、"", "M", "MEX", "MEXME" は MEX 文字列であるが、"MMEX", "EXM", "EX" などは MEX 文字列ではない。

文字列からなる集合 $S$ のスコアを $mex(|k| : k \in S)$ と定義する。

MEX 文字列 $M$ の長さ $N$ が与えられるとき、$M$ の部分文字列である MEX 文字列を互いに重ならないように選択して作ることができる集合のスコアの最大値を出力せよ。$M$ の部分文字列が重ならないとは、$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