Условие недоступно на русском языке
J. MEX의 MEX
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

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

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

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

문자열로만 이루어진 집합 S의 점수를 mex(|k|: k ∈ S)이라고 하자.

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

Input

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

각 테스트케이스의 첫째 줄에는 MEX 문자열 M의 길이 N이 주어진다. (1 ≤ N ≤ 1018)

Output

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

Example
Input
5
1
3
4
8
324513245432
Output
2
2
3
4
805621