세종대왕돈까스

세종대왕돈까스는 "세종대 왕돈까스"일까 "세종대왕 돈까스"일까?

알파벳 소문자로만 이루어진 문자열 $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)$

각 테스트 케이스마다 문제에서 요구하는 정답을 한 줄에 하나씩 출력한다.