33942번 - MEX의 MEX

문제

$\text{mex}(S)$는 집합 $S$에 포함되지 않는 가장 작은 음이 아닌 정수이다.

문자열 $X$의 부분 문자열이란 길이가 0ドル$ 이상인 $X$의 연속된 일부분을 말한다.

'M', 'E', 'X'가 순서대로 번갈아 등장하는 길이 0ドル$ 이상의 문자열을 MEX 문자열 이라고 하자. 예를 들어 ", 'M', 'MEX', 'MEXME'는 MEX 문자열이지만 'MMEX', 'EXM', 'EX' 등은 MEX 문자열이 아니다.

문자열로 이루어진 집합 $S$의 점수를 $\textrm{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})$

출력

테스트케이스마다 집합의 점수의 최댓값을 출력한다.

제한

힌트