세종대왕돈까스
세종대왕돈까스는 "세종대 왕돈까스"일까 "세종대왕 돈까스"일까?
알파벳 소문자로만 이루어진 문자열 $S$가 주어질 때, 문자열을 길이가 $1$ 이상인 두 문자열로 분할하는 서로 다른 방법은 몇가지일까?
예를 들어, aaaa를 두 문자열로 분할하는 서로 다른 방법은 a aaa로 나누는 방법과 aa aa로 나누는 방법으로 총 $2$가지이다.
이때 a aaa로 나누는 방법과 aaa a로 나누는 방법처럼 순서만 다른 경우는 동일하다고 가정한다.
입력
첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1\leq T\leq1\,000)$
두 번째 줄부터 $T$개의 줄에 걸쳐 알파벳 소문자로만 이루어진 문자열 $S$가 주어진다. $(1\leq |S|\leq20\,000)$
출력
각 테스트 케이스마다 문제에서 요구하는 정답을 한 줄에 하나씩 출력한다.
예제 입력 1
3 aaaa abcd ababab
예제 출력 1
2 3 4