$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\leq T\leq 100\,000$)

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

Output

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

Examples

Input 1

5
1
3
4
8
324513245432

Output 1

2
2
3
4
805621