MEX의 MEX

시간 제한1초메모리 제한1024 MB

요약
M, E, X가 번갈아 나오는 MEX 문자열의 길이 N이 주어질 때, 겹치지 않는 MEX 문자열 부분 문자열 길이 집합의 mex 최댓값을 구한다.
난이도

보통10점 중 6점

유형
수학, 그리디, 조합론, 동적 계획법
정답자
아직 제출이 없습니다

문제

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

문자열 XX의 부분 문자열이란 길이가 00 이상인 XX의 연속된 일부분을 말한다.

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

문자열로 이루어진 집합 SS의 점수를 mex(∣k∣:k∈S)\textrm{mex}(|k|:k\in S)이라고 하자.

MEX 문자열 MM의 길이 NN이 주어질 때 MM의 MEX 문자열인 부분 문자열을 겹치지 않고 선택해 만들 수 있는 집합의 최대 점수를 출력하라. MM 부분문자열이 겹치지 않는다는 것은 MM의 모든 문자는 많아야 하나의 부분 문자열에만 포함된다는 것이다.

입력

첫째 줄에 테스트케이스의 개수 TT가 주어진다. (1≤T≤100,000)(1 \leq T \leq 100\\,000)

각 테스트케이스의 첫째 줄에는 MEX 문자열 MM의 길이 NN이 주어진다. (1≤N≤1018)(1 \leq N \leq 10^{18})

출력

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

예제1

  1. 예제 1

    입력
    5
1
3
4
8
324513245432
    예상 출력
    2
2
3
4
805621